Порядок роста

Мы сделали замечание по поводу вычисления порядка роста количества основных операций алгоритма для достаточно больших размеров входных данных? Дело в том, что при малых размерах входных данных невозможно заметить разницу во времени выполнения между эффективным и неэффективным алгоритмом. Например, при вычислении НОД двух небольших чисел, совершенно непонятно во сколько раз алгоритм Евклида работает быстрее двух других. Непонятным остается также вопрос, почему нас так волнует, какой из алгоритмов быстрее и во сколько раз. И только тогда, когда нужно вычислить НОД двух очень больших чисел, все эти вопросы, связанные с разной эффективностью алгоритмов, выходят на первый план и становятся понятными. Для больших значений n вычисляют порядок роста функции.

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

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

Вот почему в случае, когда нужно только определить порядок роста количества основных операций алгоритма с точностью до постоянного множителя, мы будем опускать основание логарифма и записывать просто: log n. Существует и другая крайность: показательная функция 2ⁿ и функция вычисления факториала n!. Обе эти функции имеют настолько высокий порядок роста, что его значение становится астрономически большим уже при умеренных значениях n.

Например, чтобы выполнить 2¹⁰⁰ операций компьютеру, имеющему производительность в один триллион операций (10¹²) в секунду, понадобиться без малого 4 • 10¹⁰ лет! Однако это ничто по сравнению со временем, которое затратит тот же компьютер на выполнение 100! операций. Его даже нельзя сравнить со временем жизни планеты Земля, которое, по приблизительным оценкам, составляет 4.5 миллиарда (4.5 • 10⁹) лет. Несмотря на существенную разницу между порядком роста показательной функции 2ⁿ и функции n!, довольно часто говорят, что обе функции имеют экспоненциальный порядок роста. Однако, строго говоря, такое утверждение верно только для первой из этих функций. Подводя итог, можно сформулировать следующий вывод: С помощью алгоритмов, в которых количество выполняемых операций растет по экспоненциальному закону, можно решить лишь задачи очень малых размеров.

Существует еще один способ оценки качественного различия в порядке роста функций. Необходимо рассмотреть реакцию функции на двукратное увеличение значения параметра n. Для функции log₂n это приведет к увеличению значения всего на 1, так как log₂2n = log₂2 + log₂ n = = 1 + log₂n. Линейная функция увеличит значение в два раза. Значение функции nlog₂ n увеличится чуть больше, чем в два раза. Квадратичная n² и кубическая n³ функции увеличатся в четыре и восемь раз, соответственно, поскольку (2n)² = 4n² и (2n)³ = 8n³. Значение функции 2ⁿ увеличится в квадрате, поскольку 2²ⁿ = (2ⁿ)² Что касается функции n!, то ее значение увеличится намного больше, чем значение любой из рассмотренных здесь функций.

Дата добавления: 2014-01-20