Математическое толкование символа O().

Определение
O(g) - множество функций f, для которых существуют такие константы C и N, что |f(x)| <= C|g(x)| для всех x>N.
Запись f = O(g) дословно обозначает, что f принадлежит множеству O(g). При этом обратное выражение O(g) = f не имеет смысла.

В частности, можно сказать, что f(n) = 50n принадлежит O(n²). Здесь мы имеем дело с неточной оценкой. Разумеется, f(n) <= 50n² при n>1, однако более сильным утверждением было бы f(n) = O(n), так как для C=50 и N=1 верно f(n) <= Cn, n>N.

Другие виды оценок.

Наряду с оценкой O(n) используется оценка Ω(n) [читается как "Омега большое от эн"]. Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция f(n) = Ω(n²). Это значит, что даже в самом удачном случае будет произведено не менее порядка n²действий.
...В то время как оценка f(n) = O(n³) гарантирует, что в самом худшем случае действий будет порядка n³, не больше.

Также используется оценка Θ(n)["Тэта от эн"], которая является гибридом O() и Ω().
Θ(n²) является и верхней и нижней асимптотической оценкой одновременно - всегда будет выполняться порядка n² операций. Оценка Θ() существует только тогда, когда O() и Ω() совпадают и равна им.

Для рассмотренных выше алгоритмов вычисления многочлена найденные оценки являются одновременно O(), Ω() и Θ().
Если добавить к первому алгоритму проверки на x=0 в возведении в степень, то на самых удачных исходных данных(когда x=0) имеем порядка n проверок, 0 умножений и 1 сложение, что дает новую оценку Ω(n) вкупе со старой O(n²).

Как правило, основное внимание все же обращается на верхнюю оценку O(), поэтому, несмотря на "улучшение", алгоритм 2 остается предпочтительнее.

Итак, O() - асимптотическая оценка алгоритма на худших входных данных, Ω() - на лучших входных данных, Θ() - сокращенная запись одинаковых O() иΩ().

Оценка программ

Для большинства проблем существует много различных алгоритмов. Какой из них выбрать для решения конкретной задачи? Этот вопрос очень тщательно прорабатывается в программировании.

Эффективность программы (кода) является очень важной ее характеристикой. Пользователь всегда предпочитает более эффективное решение даже в тех случаях, когда эффективность не является решающим фактором.
Эффективность программы имеет две составляющие: память (или пространство) и время.

Пространственная эффективность измеряется количеством памяти, требуемой для выполнения программы.

Компьютеры обладают ограниченным объемом памяти. Если две программы реализуют идентичные функции, то та, которая использует меньший объем памяти, характеризуется большей пространственной эффективностью. Иногда память становится доминирующим фактором в оценке эффективности программ. Однако в последний годы в связи с быстрым ее удешевлением эта составляющая эффективности постепенно теряет свое значение.

Временная эффективность программы определяется временем, необходимым для ее выполнения.

Лучший способ сравнения эффективностей алгоритмов состоит в сопоставлении их порядков сложности. Этот метод применим как к временной, так и пространственной сложности. Порядок сложности алгоритма выражает его эффективность обычно через количество обрабатываемых данных.

Например, некоторый алгоритм может существенно зависеть от размера обрабатываемого массива. Если, скажем, время обработки удваивается с удвоением размера массива, то порядок временной сложности алгоритма определяется как размер массива.