1_Алгоритми_трудомісткість

1.

ТРУДОМІСТКІСТЬ АЛГОРИТМІВ ТА ЇХ
ЧАСОВІ ОЦІНКИ

2.

Елементарні операції в мові запису алгоритмів
Просте присвоювання:
а ← b.
Одновимірна індексація a [i]: s=a[3];
(адреса (a) + i * довжина елементу).
Арифметичні операції:
(*, /, -, +).
Операції порівняння:
a < b.
Логічні операції
{or, and, not}

3.

конструкція «Послідовного переходу»
F«Послідовного переходу» = f1 + … + fk,
де k – кількість блоків.

4.

конструкція «Розгалуження»
F «Розгалуження» = fthen * p + felse * (1-p)

5.

конструкція «Цикл»
F «цикл» = 1+3*N+N*f«тіло циклу»

6.

Приклад 1. Знайти суму елементів квадратної
матриці.
SumM (A, n; Sum)
Sum ← 0
For i ← 1 to n
For j ← 1 to n
Sum ← Sum + A[i,j]
end for
Return (Sum)
End
FA (n) = 1 +(1 + 3*n + n * (1 + 3*n +n *1)) =
= 1 + 1 + n * (3 +1 + n * 4) = 4 n^2 +4 * n +2 = Q (n^2)
N=10, O(n)=442
N=100 O(100)=400402

7.

Приклад 2. Пошук максимуму в масиві
MaxS (S,n; Max)
1. Найгірший випадок
Max ← S[1]
FA ^(n)=1+1+1+ (n-1) (3+2+2)=7 n – 4 =
О(n)
For i ← 2 to n
if Max < S[i]
then Max ← S[i]
end for
234689
985432 589234
2. Кращий випадок
FA∨ (n)=1+1+1+ (n-1) (3+2)=5 n – 2
= Ω(n)
3. Середній випадок
FA(n)=1 + (n-1) (3+2) + 2 (Ln(n) + γ)
= 5 n +2 Ln(n) – 4 +2 γ = Θ(n)

8.

Визначення складності коду

9.

Запитання
Правильна відповідь

10.

Запитання
Правильна відповідь

11.

Запитання
Правильна відповідь

12.

Запитання
4. Визначити складність коду
Правильна відповідь

13.

Асимптотична складність

14.

CrСкладність алгоритму
Розмір
10
20
30
40
50
60
Складність
n
0,00001 cек 0,00002 cек 0,00003 cек 0,00004 cек 0,00005 cек
0,00005 cек
n^2
0,0001 сек
0,0004 сек
0,0009 сек
0,0016 сек
0,0025 сек
0,0036 сек
n^3
0,001 сек
0,008 сек
0,027 сек
0,064 сек
0,125 сек
0,216 сек
n^5
0,1 сек
3,2 сек
24,3 сек
1,7 хв
5,2 хв
13 хв
2^n
0,0001 сек
1 сек
17,9 хв
12,7 діб
35,7 століть
366 століть
3^n
0,059 сек
58 хв
6,5 років
3855 століть
2∙10^8 ст
1,3∙10^13 ст

15.

Сортування вибіркою полягає у пошуку мінімального значення
елемента в масиві, і переміщення цього значення в початок масиву.

16.

Сортування вставкою ділить масив на дві частини: сортовану та
несортовану. Метод порівнює наступний елемент непосортованої
частини з послідовними елементами посортованої та вставляє у
потрібне місце
Масив: 3 3 7 1 2 5 0

17.

Сортування бульбашкою . Проходимо масивом кілька разів, на
кожному етапі переміщуючи найбільше значення з невідсортованих
елементів у кінець масиву.