Элементы теории алгоритмов

Август 10, 2022

Главная
Информатика
Элементы теории алгоритмов

Содержание

2. Что такое сложность вычислений? Задачи теории алгоритмов: существует ли алгоритм решения задачи? можно ли им воспользоваться?
3. Временнáя сложность T – количество элементарных операций универсального исполнителя (компьютера) Временная сложность алгоритма – функция T(n).
4. Временнáя сложность Задача 3. Отсортировать все элементы массива по возрастанию методом выбора. нц для i от
5. Сравнение алгоритмов по сложности при n при n > 100:
6. Асимптотическая сложность Асимптотическая сложность – это оценка скорости роста количества операций при больших значениях N. сложность
7. Асимптотическая сложность сложность O(N3) ⇔ T(N) ≤ c⋅ N3 для N ≥ N0 кубичная сложность O(2N)
8. Асимптотическая сложность Алгоритм относится к классу O( f(N) ), если найдется такая постоянная c, что начиная
9. Асимптотическая сложность
10. Алгоритмы поиска Линейный поиск nX:= 0 нц для i от 1 до n если A[i] =
11. Алгоритмы поиска Двоичный поиск L:= 1; R:= n + 1 нц пока L c:= div(L +
12. Алгоритмы сортировки Метод «пузырька» нц для i от 1 до n-1 нц для j от n-1
13. Алгоритмы сортировки Сортировка подсчётом цел C[1:MAX] нц для i от 1 до MAX C[i]:= 0 кц
15. Скачать презентацию

Слайд 2

Что такое сложность вычислений?
Задачи теории алгоритмов:
существует ли алгоритм решения задачи?
можно ли

им воспользоваться?

Шахматы:
алгоритм существует (конечное число позиций)
полный перебор нереален

Требования к алгоритму:
быстродействие
минимальный расход памяти

временнáя сложность

пространственная сложность

Слайд 3

Временнáя сложность
T – количество элементарных операций универсального исполнителя (компьютера)
Временная сложность алгоритма

– функция T(n).

Задача 1. Вычислить сумму первых трёх элементов массива (при n ≥ 3).

Sum:= A[1] + A[2] + A[3]

T(n) = 3

2 сложения + запись в память

Задача 2. Вычислить сумму всех элементов массива.

Sum:= 0
нц для i от 1 до n
Sum:= Sum + A[i]
кц

T(n) = 2n + 1

n сложений, n+1 операций записи

Слайд 4

Временнáя сложность
Задача 3. Отсортировать все элементы массива по возрастанию методом выбора.

нц для i от 1 до n-1
nMin:= i;
нц для j от i+1 до n
если A[i] < A[nMin] то nMin:= j все
кц
если nMin <> i то
c:= A[i]; A[i]:= A[nMin]; A[nMin]:= c
все
кц

Число сравнений:

Число перестановок:

зависит от данных

Слайд 5

Сравнение алгоритмов по сложности
при n < 100:
при n > 100:

Слайд 6

Асимптотическая сложность
Асимптотическая сложность – это оценка скорости роста количества операций при

больших значениях N.

сложность O(N) ⇔ T(N) ≤ c⋅ N для N ≥ N0

постоянная

линейная

сумма элементов массива:

T(N) = 2⋅ N – 1 ≤ 2⋅ N для N ≥ 1 ⇒ O(N)

сложность O(N2) ⇔ T(N) ≤ c⋅ N2 для N ≥ N0

квадратичная

сортировка методом выбора:

для N ≥ 0 ⇒ O(N2)

Слайд 7

Асимптотическая сложность
сложность O(N3) ⇔ T(N) ≤ c⋅ N3 для N ≥

N0

кубичная

сложность O(2N)

сложность O(N!)

задачи оптимизации, полный перебор вариантов

Факториал числа N: N ! = 1 ⋅ 2 ⋅ 3 … ⋅ N

N = 100,
1 млрд оп/с

Слайд 8

Асимптотическая сложность
Алгоритм относится к классу O( f(N) ), если найдется такая

постоянная c, что начиная с некоторого N = N0 выполняется условие
T(N) ≤ c⋅ f (N)

это верхняя оценка!

O( N ) ⇒ O( N2 ) ⇒ O( N3 ) ⇒ O( 2N )

«Алгоритм имеет сложность O(N2)».

обычно – наиболее точная верхняя оценка!

Слайд 9

Асимптотическая сложность

Слайд 10

Алгоритмы поиска
Линейный поиск
nX:= 0
нц для i от 1 до n

если A[i] = X то
nX:= i
выход
все
кц

сложность O(n)

Слайд 11

Алгоритмы поиска
Двоичный поиск
L:= 1; R:= n + 1
нц пока L <

R - 1
c:= div(L + R, 2)
если X < A[c] то
R:= c
иначе
L:= c
все
кц

сложность O(log n)

n = 2m

T(n) = m + 1

T(n) = log2 n + 1

log2 n

основание роли не играет

Слайд 12

Алгоритмы сортировки
Метод «пузырька»
нц для i от 1 до n-1
нц для

j от n-1 до i шаг -1
если A[j] > A[j+1] то
c:= A[j]; A[j]:= A[j+1]; A[j+1]:= c;
все
кц
кц

сложность O(n2)

сравнений:

присваиваний при перестановках:

Слайд 13

Алгоритмы сортировки
Сортировка подсчётом
цел C[1:MAX]
нц для i от 1 до MAX

C[i]:= 0
кц

нц для i от 1 до n
C[A[i]]:= C[A[i]] + 1
кц

обнулить массив счётчиков

подсчитать, сколько каких чисел

k:= 1
нц для i от 1 до MAX
нц для j от 1 до C[i]
A[k]:= i
k:= k + 1
кц
кц

заполнить массив заново

сложность O(n)