- описание анализа алгоритма;
- объяснение принципов выбора подсчитываемых операций;
- проведение анализа в наилучшем, наихудшем и среднем случаях;
- работа с логарифмами, вероятностями и суммированием;
- описание функций θ(f), Ω(f), O(f), скорости роста и порядка алгоритма;
- использование дерева решений для определения нижней границы сложности;
- вывод формулы общего члена последовательности из простых рекуррентных соотношений.
Количество "времени", необходимое для выполнения алгоритма - это приблизительное число операций, выполняемых алгоритмом. Относительное "время" выполнения алгоритма - это вычислительная сложность алгоритма.
Алгоритм не становится лучше, если его перенести на более быстрый компьютер, или хуже, если его исполнять на более медленном. Фактическое количество операций алгоритма на тех или иных входных данных тоже не представляет большого интереса.
Интересна зависимость числа операций конкретного алгоритма от размера входных данных. Алгоритмы сравниваются по скорости роста числа операций. Скорость роста играет ключевую роль, поскольку при небольшом размере входных данных алгоритм A может требовать меньшего количества операций, чем алгоритм B, но при росте объема входных данных ситуация может поменяться на противоположную.
