Сложность вычислений. Требования к алгоритму

Что такое сложность вычислений?
Требования к алгоритму:
Быстродействие – временная сложность
Минимальный расход
памяти - пространственная сложность

Временнáя сложность
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 операций записи)

Задача 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
все
кц
Число сравнений:
Число перестановок:

Сравнение алгоритмов по сложности

Асимптотическая сложность
Асимптотическая сложность – это скорость роста количества операций при больших значениях 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)

Асимптотическая сложность
сложность O(n3) ⇔ T(n) ≤ c⋅ n3 для n ≥ n0
Алгоритм имеет асимптотическую сложность O ( f (n) ), если найдется такая постоянная c, что начиная с некоторого n = n0 выполняется условие
T(n) ≤ c⋅ f (n)

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

Алгоритмы поиска
Линейный поиск
nX:= 0
нц для i от 1 до n
если A[i] = X то
nX:= i
выход
все
кц
сложность O(n)

Алгоритмы поиска
Двоичный поиск
L:= 1; R:= n + 1
нц пока L < R - 1
c:= div(L + R, 2)
если X < A[c] то
R:= c
иначе
L:= c
все
кц
n = 2m шагов T(n) = m + 1
T(n) = log2 n + 1
сложность O(log n) основание логарифма роли не играет

Алгоритмы сортировки
Метод «пузырька»
нц для 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)

Алгоритмы сортировки
Сортировка подсчётом
цел C[1:MAX] Все значения [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)
кц
кц