Алгоритмы и анализ сложности. Анализ трудоемкости алгоритмов

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

Типичные случаи для трудоемкости

Функции трудоемкости
На выполнение 1018 действий при скорости
109 действий в 1 секунду потребуется более 30 лет.

Соотношения для оценки и сравнения трудоемкостей

Типы трудоемкостей

Алгоритмы, основанные на сравнениях

Поиск в массиве

1-я теорема о временной сложности

1-я теорема о временной сложности

Примеры использования 1-й теоремы

2-я теорема о временной сложности

2-я теорема о временной сложности

2-я теорема о временной сложности