О-сложность алгоритмов.

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

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

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

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

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

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

Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).
Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.

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

Существуют три важных правила для определения сложности.
1. O(k*f)=O(f)
2. O(f*g)=O(f)*O(g) или O(f/g)=O(f)/O(g)
3. O(f+g) равна доминанте O(f) и O(g)

Здесь k обозначает константу, a f и g - функции.

Первое правило декларирует, что постоянные множители не имеют значения для определения порядка сложности.
1,5*N=O(N)

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

O((17*N)*N) = O(17*N)*O(N) = O(N)*O(N)=O(N*N) = O(N²)

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

O(N⁵+N²)=O(N⁵)

Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).

 

Программист должен уметь проводить анализ алгоритмов и определять их сложность.

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

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

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