Скорость роста сложности алгоритма играет важную роль, и мы видели, что скорость роста определяется старшим, доминирующим членом формулы. Поэтому мы будем пренебрегать младшими членами, которые растут медленнее. Отбросив все младшие члены, мы получаем то, что называется порядком функции или алгоритма, скоростью роста сложности которого она является.
Алгоритмы можно сгруппировать по скорости роста их сложности:
Алгоритмы можно сгруппировать по скорости роста их сложности:
- алгоритмы, сложность которых растет по крайней мере так же быстро, как данная функция;
- алгоритмы, сложность которых растет с той же скоростью;
- и алгоритмы, сложность которых растет медленнее, чем эта функция.
Омега большое
Класс функций, растущих по крайней мере так же быстро, как f, мы обозначаем через Ω(f) (читается омега большое). Функция g принадлежит этому классу, если при всех значениях аргумента n, больших некоторого порога n0, значение g(n) > cf(n) для некоторого положительного числа с. Можно считать, что класс Ω(f) задается указанием своей нижней границы: все функции из него растут по крайней мере так же быстро, как f.Мы занимаемся эффективностью алгоритмов, поэтому класс Ω(f) не будет представлять для нас большого интереса: например, в Ω(n2) входят все функции, растущие быстрее, чем n2, скажем n3 и 2n.
О большое
На другом конце спектра находится класс O(f) (читается о большое). Этот класс состоит из функций, растущих не быстрее f. Функция f представляет собой верхнюю границу для класса O(f). С формальной точки зрения функция g принадлежит классу О(f), если g(n) <= cf(n) для всех n, больших некоторого порога n0, и для некоторой положительной константы с.Этот класс чрезвычайно важен для нас. Про два алгоритма нас будет интересовать, принадлежит ли сложность первого из них классу "о большое" от сложности второго. Если это так, то, значит, второй алгоритм не лучше первого решает поставленную задачу.
Описание класса О большое
Проверить, принадлежит ли данная функция классу О(f), можно двумя способами: либо с помощью данного выше определения, либо воспользовавшись следующим описанием: g ∈ O(f), если
для некоторой константы с. Это означает, что если предел отношения g(n) / f(n) существует и он меньше бесконечности, то g ∈ O(f). Для некоторых функций это не так-то просто проверить. По правилу Лопиталя, в таком случае можно заменить предел самих функций пределом их производных.Тета большое
Через Θ(f) (читается тета большое) мы обозначаем класс функций, растущих с той же скоростью, что и f. С формальной точки зрения этот класс представляет собой пересечение двух предыдущих классов, Θ(f) = Ω(f) ∩ O(f).При сравнении алгоритмов нас будут интересовать такие, которые решают задачу быстрее, чем уже изученные. Поэтому, если найденный алгоритм относится к классу Θ, то он нам не очень интересен.
