Основные правила анализа алгоритмов

Основным критерием эффективности алгоритма является его временная сложность. При нахождении времени выполнения итеративных и рекурсивных алгоритмов используют различные методы и приемы, опирающиеся на некоторые базовые принципы.

Пусть и ‑ время выполнения двух фрагментов и , имеет степень роста, а ‑ . Тогда , т.е. время последовательного выполнения фрагментов и, имеет степень роста .

Правило сумм, данное выше, используется для вычисления времени последовательного выполнения программных фрагментов с циклами и ветвлениями. Пусть есть три фрагмента с временами выполнения соответственно , и (под обозначением мы будем понимать двоичный логарифм). Тогда время последовательного выполнения всех трех фрагментов имеет порядок , это то же самое, что . В общем случае время выполнения конечной последовательности фрагментов алгоритма, без учета констант, имеет порядок фрагмента с наибольшим временем вы­полнения. Иногда возможна ситуация, когда порядки роста времен нескольких фраг­ментов несоизмеримы (ни один из них не больше, чем другой, но они и не равны). Для примера рассмотрим два фрагмента с временем выполнения O(f(n)) и O(g(n)), где

В данном случае правило сумм можно применить непосредственно и получить время выполнения , т.е. п⁴ при п четном и п³, если п нечетно. Из правила сумм также следует, что если для всех п, превышающих п₀, то выражение эквивалентно . Например, то же самое что .

Правило произведений заключается в следующем. Если и имеют степени роста и соответственно, то произведение имеет степень роста . Из пра­вила произведений следует, что эквивалентно , если с — положительная константа. Например, эквивалентно _.