О - нотация оценки сложности алгоритмов.

О-нотация

Для оценивания трудоемкости алгоритмов была введена специальная система обозначений – так называемая О-нотация. Эта нотация позволяет учитывать в функции f (n) лишь наиболее значимые элементы, отбрасывая второстепенные.
Например, в функции f (n) = 2n2 + n – 5 при достаточно больших n компонента n2 будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида О(n2 ).
Аналогично, для функции f (n) = 2n + 3n3 – 10 начиная с некоторого n первое слагаемое будет превосходить второе и поэтому данную функцию можно описать оценкой О(2n).
Важность О-оценивания состоит в том, что оно позволяет описывать характер поведения функции f(n) с ростом n: насколько быстро или медленно растет эта функция.
О-оценка позволяет разбить все основные функции на ряд групп в зависимости от скорости их роста:

постоянные функции типа О(1), которые с ростом n НЕ растут (в оценивании алгоритмов этот случай встречается крайне редко, но все-таки встречается!)
функции с логарифмической скоростью роста О(log 2 n)
функции с линейной скоростью роста О(n)
функции с линейно–логарифмической скоростью роста О(n*log 2 n)
функции с квадратичной скоростью роста О(n2 )
функции со степенной скоростью роста О(na) при а>2
функции с показательной или экспоненциальной скоростью роста О(2n)
функции с факториальной степенью роста О(n!)

В этом списке функции упорядочены именно по критерию скорости роста: сначала идут медленно растущие функции, потом – все более быстро растущие. Графики некоторых функций приведены на рисунке.

Отсюда можно сделать несколько выводов.

При выборе однотипных алгоритмов предпочтение (при прочих равных условиях) следует отдавать алгоритмам с наименьшей скоростью роста трудоемкости, поскольку они позволят за одно и то же время решить задачи с большей размерностью
Если заранее известно, что размерность решаемых задач невелика, но зато число их повторений очень большое, имеет смысл рассмотреть возможность использования алгоритмов не с самой лучшей оценкой, поскольку при малых n “лучшие” алгоритмы могут вести себя хуже, чем “плохие” (это можно заметить по графику в области начала координат)
Алгоритмы класса О(2n) и О(n!) следует использовать с большой осторожностью, учитывая катастрофический рост их трудоемкости уже при n>100. Например, если число базовых операций определяется соотношением 2n, то при n=100 это число будет примерно равно 1030, и если одна базовая операция выполняется за 1 микросекунду, то это потребует около 1024 секунд, т.е. порядка 1016 лет. К сожалению, задачи с подобной трудоемкостью довольно часто встречаются на практике и их точное решение пока невозможно даже на сверхбыстрых суперкомпьютерах!

Как быть с оценкой трудоемкости программы в целом, если в программе используется несколько алгоритмов, решающих свои конкретные задачи? Есть два основных способа взаимодействия алгоритмов – последовательное и вложенное. При последовательном выполнении алгоритмов с оценками O(f1), O(f2), …, O(fk) общая трудоемкость определяется трудоемкостью алгоритма с максимальным значением:
O (программы) = Max (O(f1), O(f2), . . ., O(fk))
При вложенном выполнении общая трудоемкость есть произведение оценок вложенных друг в друга алгоритмов: O(программы) = O(f1)*O(f2)*O(f3)