Быстрорастущие функции доминируют над функциями с более медленным ростом. Поэтому если сложность алгоритма представляет собой сумму двух или нескольких таких функций, то можно отбросить все функции, кроме тех, которые растут быстрее всего. Если, например, алгоритм делает x3-30x сравнений, то его сложность растет как x3. Причина этого в том, что уже при x = 100 входных данных разница между x3 и x3-30x составляет лишь 0,3%.
Скорость роста сложности алгоритма определяется старшим, доминирующим членом формулы. Поэтому можно пренебрегать младшими членами, которые растут медленнее. Отбросив все младшие члены, мы получаем то, что называется порядком функции или алгоритма, скоростью роста сложности которого она является.
Алгоритмы, сложность которых:
- растёт по крайней мере так же быстро, как данная функция
При занятии эффективностью алгоритмов, класс Ω(f) не представляет большого интереса: например в Ω(n2) входят все функции, растущие быстрее, чем n2, скажем, n3 и 2n.
- растёт с той же скоростью
При сравнении алгоритмов интересны такие, которые решают задачу быстрее, чем уже известные. Поэтому если найденный алгоритм относится к классу Θ, то он не очень интересен.
- растёт медленнее, чем эта функция
Алгоритмы, сложность которых:
- растёт по крайней мере так же быстро, как данная функция
При занятии эффективностью алгоритмов, класс Ω(f) не представляет большого интереса: например в Ω(n2) входят все функции, растущие быстрее, чем n2, скажем, n3 и 2n.
- растёт с той же скоростью
При сравнении алгоритмов интересны такие, которые решают задачу быстрее, чем уже известные. Поэтому если найденный алгоритм относится к классу Θ, то он не очень интересен.
- растёт медленнее, чем эта функция
Этот класс чрезвычайно важен. При сравнении двух алгоритмов интересно, принадлежит ли сложность первого из них классу "о большое" от сложности второго. Если это так, то значит второй алгоритм не лучше первого решает поставленную задачу.
Комментарии
Отправить комментарий