Точное знание количества операций, выполненных алгоритмом, не играет существенной роли в анализе алгоритмов. Куда более важным оказывается скорость роста этого числа при возрастании объема входных данных. Она называется скоростью роста алгоритма. Небольшие объемы данных не столь интересны, как то, что происходит при возрастании этих объемов.
 |
| Графики четырех функций: x2 / 8 3 * x - 2 x + 10 2 * logx |
Если внимательно посмотреть на графики четырех функций, то можно отметить следующие особенности поведения графиков функций.
Относительная высота значений функций также зависит от того, большие или маленькие значения переменной мы рассматриваем. Сравним значения функций при х = 2. Функцией с наименьшим значением в этой точке является x2 / 8, а с наибольшим — функция х + 10. Однако с возрастанием х функция x2 / 8 становится и остается впоследствии наибольшей.
Подводя итоги, при анализе алгоритмов нас будет интересовать скорее класс скорости роста, к которому относится алгоритм, нежели точное количество выполняемых им операций каждого типа. Относительный «размер» функции будет интересовать нас лишь при больших значениях переменной х.
Некоторые часто встречающиеся классы функций приведены в нижеследующей таблице. В этой таблице собраны значения функций из данного класса на широком диапазоне значений аргумента.
Видно, что при небольших размерах входных данных значения функций отличаются незначительно, однако при росте этих размеров разница существенно возрастает. Поэтому мы и будем изучать, что происходит при больших объемах входных данных, поскольку на малых объемах принципиальная разница оказывается скрытой.
Быстрорастущие функции доминируют над функциями с более медленным ростом. Поэтому если мы обнаружим, что сложность алгоритма представляет собой сумму двух или нескольких таких функций, то будем часто отбрасывать все функции кроме тех, которые растут быстрее всего.
Если, например, мы установим при анализе алгоритма, что он делает x3 - 30x сравнений, то мы будем говорить, что сложность алгоритма растет как x3. Причина этого в том, что уже при x = 100 входных данных разница между x3 и x3 - 30x составляет лишь 0,3%.
- Функция, содержащая x2, сначала растет медленно, однако чем больше x, тем выше скорость роста функции.
- Скорость роста функций, содержащих x, постоянна на всем интервале значений переменной.
- Функция 2logx вообще кажется постоянной, однако это обман зрения. На самом деле она растет, только очень медленно.
 |
| Графики четырех функций: x2 / 8 3 * x - 2 x + 10 2 * logx |
Относительная высота значений функций также зависит от того, большие или маленькие значения переменной мы рассматриваем. Сравним значения функций при х = 2. Функцией с наименьшим значением в этой точке является x2 / 8, а с наибольшим — функция х + 10. Однако с возрастанием х функция x2 / 8 становится и остается впоследствии наибольшей.
Подводя итоги, при анализе алгоритмов нас будет интересовать скорее класс скорости роста, к которому относится алгоритм, нежели точное количество выполняемых им операций каждого типа. Относительный «размер» функции будет интересовать нас лишь при больших значениях переменной х.
Некоторые часто встречающиеся классы функций приведены в нижеследующей таблице. В этой таблице собраны значения функций из данного класса на широком диапазоне значений аргумента.
 |
| Классы роста функций |
 |
| Графики функций: log2n, n, nlog2n, n2, n3, и 2n |
Видно, что при небольших размерах входных данных значения функций отличаются незначительно, однако при росте этих размеров разница существенно возрастает. Поэтому мы и будем изучать, что происходит при больших объемах входных данных, поскольку на малых объемах принципиальная разница оказывается скрытой.
Быстрорастущие функции доминируют над функциями с более медленным ростом. Поэтому если мы обнаружим, что сложность алгоритма представляет собой сумму двух или нескольких таких функций, то будем часто отбрасывать все функции кроме тех, которые растут быстрее всего.
Если, например, мы установим при анализе алгоритма, что он делает x3 - 30x сравнений, то мы будем говорить, что сложность алгоритма растет как x3. Причина этого в том, что уже при x = 100 входных данных разница между x3 и x3 - 30x составляет лишь 0,3%.
