О-СЛОЖНОСТЬ АЛГОРИТМОВ

O(1)Большинство операций в программе выполняются только раз или только несколько раз. Алгоритмами константной сложности. Любой алгоритм, всегда требующий независимо от размера данных одного и того же времени, имеет константную сложность.

О(N)Время работы программы линейно обычно, когда каждый элемент входных данных требуется обработать лишь линейное число раз.

О(N²), О(^N3), О(N^а)Полиномиальная сложность. О(N2)-квадратичная сложность, О(N3)- кубическая сложность

О(Log(N))Когда время работы программы логарифмическое, программа начинает работать намного медленнее с увеличением N. Такое время работы встречается обычно в программах, которые делят большую проблему в маленькие и решают их по отдельности.

O(N*log( N))Такое время работы имеют те алгоритмы, которые делят большую проблему в маленькие, а затем, решив их, соединяют их решения.

O(2N)Экспоненциальная сложность. Такие алгоритмы чаще всего возникают в результате подхода именуемого метод грубой силы.

Временная сложность алгоритма может быть посчитана исходя из анализа его управляющих структур.(if, for,…простые выражения)

Определение сложности алгоритма в основном сводится к анализу циклов и рекурсивных вызовов.

Например, рассмотрим алгоритм обработки элементов массива.

For i:=1 to N do

Begin

...

End;

Сложность этого алгоритма O(N), т.к. тело цикла выполняется N раз, и сложность тела цикла равна O(1).

Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью.

For i:=1 to N do

For j:=1 to N do

Begin ...

End;

Сложность этой программы О(N2).

Существуют два способа анализа сложности алгоритма: восходящий (от внутренних управляющих структур к внешним) и нисходящий (от внешних и внутренним).

Обычно решаемая задача имеет естественный "размер" (обычно количество данных ею обрабатываемых) которое мы называем N. В конечном итоге нам бы хотелось получить выражение для времени, необходимого программе для обработки данных размера N, как функцию от N. Обычно на интересует средний случай - ожидаемое время работы программы на "типичных" входных данных, и худший случай - ожидаемое время работы программы на самых плохих входных данных.

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

Несколько важных причин такого рода анализа:

1. Программы, написанные на языке высокого уровня, транслируются в машинные коды, и понять сколько времени потребуется для выполнения того или иного оператора может быть трудно.

2. Многие программы очень чувствительны к входным данным, и их эффективность может очень сильно от них зависеть. Средний случай может оказаться математической фикцией не связанной с теми данными на которых программа используется, а худший случай маловероятен.

Лучший, средний и худший случаи очень большое влияние играют в сортировке. Объем вычислений при сортировке