Теоретическая часть


Таблица и график для худшего случая



страница4/4
Дата12.08.2022
Размер1,04 Mb.
#188273
1   2   3   4
Связанные:
kursovaya

Таблица и график для худшего случая.

n

NOP

C3 = F(n)/NOP

F(n)

200

236873881

1,018774

241321002

400

1907467781

1,009339

1,925E+09

600

6451781681

1,006216

6,492E+09

800

15309815581

1,004658

1,538E+10

1000

29921569481

1,003724

3,003E+10

1200

51727043381

1,003102

5,189E+10

1400

82166237281

1,002659

8,238E+10

1600

122679151181

1,002326

1,23E+11

1800

174705785081

1,002067

1,751E+11

2000

239686138981

1,00186

2,401E+11







По графику видно, что коэффициент стремится к 1, значит формула верна. Делаем вывод: случай со случайными значениями сильно отличается от худшего случая, этим объясняется “странный” вид графика c3 для случайных значений.


Таблицы и графики для особого случая.
Массив уже отсортирован по убыванию или все элементы массива одинаковы.
Подсчёт операций в сортировке.
В лучшем случае перестановок элементов не требуется, поэтому в цикл(while(item >= 0 && get( q , item ) > temp)) не происходит ни одного входа.
F(n)=2(int temp,item;)+(цикл for (int i= 0; i < n; i++) )n * ( (объявление переменной temp) 1 + (get(q,i);) (20n+2) + (item=i-1;) 2+( while(item >= 0 && get( q , item ) > temp)) (20n+2+2) + (set(q , item+1 , temp);) (20n-2+1))=
=2+n(1+20n+2+2+2+20n+2+1+20n-2)=
=2+n(60n+8) =60n^2+8n+2

C1 = F(n)/T(n)

C2 = O(F(n))/T(n)

C3 = F(n)/NOP

C4=O(F(n))/NOP

150100,1

300000

1,012021

2,022691

204323,4

408510,6

1,005984

2,011298

172838,4

345600

1,003984

2,007521

176176,2

352293,6

1,002986

2,005637

240032

480000

1,002387

2,004508

213357

426666,7

1,001989

2,003755

221490

442937,9

1,001704

2,003218

218821,7

437606,8

1,001491

2,002815

207707,7

415384,6

1,001325

2,002502

207986,1

415944,5

1,001193

2,002252





n

T nach

T kon

T kon- T nach

NOP

O(F(n))=60n^3

F(n)

200

4259778

4259794

16

2373076

4800000

2401602

400

4259794

4259841

47

9546076

19200000

9603202

600

4259841

4259966

125

21519076

43200000

21604802

800

4259966

4260184

218

38292076

76800000

38406402

1000

4260184

4260434

250

59865076

120000000

60008002

1200

4260434

4260839

405

86238076

172800000

86409602

1400

4260839

4261370

531

117411076

235200000

117611202

1600

4261370

4262072

702

153384076

307200000

153612802

1800

4262072

4263008

936

194157076

388800000

194414402

2000

4263008

4264162

1154

239730076

480000000

240016002













Выводы.
Реализована сортировка простой вставкой линейного списка типа дек. Этот алгоритм реализован в виде программы на языке C++, с использованием методов объектно-ориентированного программирования. При этом создан абстрактный тип данных Deque. Корректность работы алгоритма сортировки, подтверждена посредством тестирования произвольными наборами входных данных, вводимых с клавиатуры.
Произведен расчёт трудоёмкости предложенного алгоритма посредством построения функции роста, которая оценивалась прямым подсчетом операций, выполняемых программой в худшем случае(наиболее неблагоприятная комбинация входных данных). Установлено, что функция роста имеет асимптотический характер O(N3), где N – длина очереди.
При сортировке элементов линейного списка был обнаружен особый случай, при котором время программы и количество операций существенно отличались от случайных значений. Сложность алгоритма стала равной O(n^2), так как не требовалось переставлять элементы местами. При этом коэффициент пропорциональности между экспериментальной функцией роста примерно равен 2,0 для варианта случайного заполнения очереди и от 1,001 до 1,01 для особого случая.
Список источников.
Структуры данных и алгоритмы. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. – М.: Издательский дом «Вильямс», 2016
Алгоритмы: построение и анализ. Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М.: МЦНМО, 2013.
Седжвик, Роберт, Уэйн, Кевин. Алгоритмы на Java, 4-е изд. : Пер. с англ. – М. ООО “И.Д. Вильямс”, 2013. – 848 с. : ил. – Парал. тит. англ.

Поделитесь с Вашими друзьями:
1   2   3   4




База данных защищена авторским правом ©psihdocs.ru 2022
обратиться к администрации

    Главная страница