logo
shpori (1) / shpori (1)

1.Трудоемкость алгоритмов

Размер входа - число ячеек памяти, заним вход данными при разумном кодировании.

Элементарные операции:

1) Вызов функции

2) Логические операции

3) Арифметические операции

4) Операции присваивания

5) Обращение к элементу массива по его индексу

Время работы алгоритма на входных данных X – это число элементарных операций, выполняемых алгоритмом при обработке X.

Трудоемкость в худшем случае

Пусть имеется некоторый алгоритм A

TA: N®N TA(n) – максимальное время работы алгоритма A на входе размера n

TA(n) – трудоемкость алгоритма A

O-символика

f(n) = O(g(n)) если и только если существует константа С>0 такая, что f(n)£Cg(n) для любого n. Если TA(n) = O(g(n)), то говорят, что O(g(n)) – временнáя сложность алгоритма A. Это значит, что в самом худшем случае на входе размера n наш алгоритм будет работать не более Сn времени.

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

Пусть n – размер входа алгоритма

  1. O(n) – линейная сложность

  2. O(nk) – полиномиальная сложность

  3. O(kn) – экспоненциальная сложность

  4. O(nlogn), O(n!),…