Алгоритмы неформально. Инструкция для начинающих питонистов - [30]
1
3 или менее (есть три папки для сравнения, необходимо выполнить сравнение от 1 до всех папок)
1
…
…
…
…
Взять n-ю папку со старой полки и поставить ее на новую полку (на которой сейчас стоят n – 1 папок)
1
n – 1 или менее (есть n – 1 папок для сравнения, необходимо выполнить сравнение от 1 до всех папок)
1
Если просуммировать все шаги, описанные в таблице, то мы получим следующие значения:
• шаги, необходимые для снятия папок: n (1 шаг на снятие каждой из n папок);
• шаги, необходимые для сравнения: до 1 + 2 + ... + (n – 1);
• шаги, необходимые для вставки папок: n (1 шаг на вставку каждой из n папок).
Суммируя эти значения, мы получаем выражение следующего вида:
максимальное_количество_шагов = n + (1 + 2 + ... + n).
Выражение можно упростить с помощью удобного тождества:
Если воспользоваться этим тождеством, просуммировать все значения и упростить, то можно обнаружить, что общее количество необходимых шагов равно
Наконец-то у нас появилось очень точное выражение для максимального количества шагов, которые могут потребоваться для выполнения сортировки методом вставки. Но как ни странно, это выражение может быть даже слишком точным по нескольким причинам. Одна из них такова: мы вычислили максимальное количество шагов, а минимальное и среднее количество может быть намного меньше, и почти каждый список, который мы захотим отсортировать, потребует меньшего количества шагов. Вспомните неровность кривой, изображенной на рис. 4.1, — всегда существует разброс во времени выполнения алгоритма в зависимости от выбора входных данных.
Другая причина, по которой выражение для максимального количества шагов может быть слишком точным, заключается в том, что знание количества шагов алгоритма наиболее важно для больших значений n, но для очень больших n небольшая часть выражения начинает превосходить все остальные по важности из-за резкого расхождения скоростей роста разных функций.
Возьмем выражение n2 + n. Оно состоит из двух слагаемых: n2 и n. Для n = 10 выражение n2 + n равно 110, которое на 10 % больше n2. Для n = 100 выражение n2 + n равно 10 100, которое всего на 1 % больше n2. С ростом n слагаемое n2 становится более важным, чем слагаемое n, поскольку квадратичные функции растут намного быстрее линейных. Таким образом, если у нас есть один алгоритм, который состоит из n2 + n шагов, и другой алгоритм, который выполняется за n2 шагов, с ростом n разность между ними будет становиться все менее и менее существенной. Оба алгоритма выполняются близко к n2 шагов.
Нотация «О большое»
Утверждение о том, что алгоритм выполняется более или менее за n2 шагов, обеспечивает разумный баланс между нужной точностью и компактностью (и случайностью). Подобные отношения «более или менее» более точно выражаются в нотации «О большое» (O — сокращение от Order, то есть порядок). Говорят, что конкретный алгоритм «находится в зависимости “O большое” от n2» или «имеет сложность O(n2)», если в худшем случае он выполняется более или менее за n2 шагов при больших n. Техническое определение гласит, что функция f(x) находится в зависимости «O большое» от функции g(x), если существует некоторая константа M, при которой абсолютное значение f(x) всегда меньше M×g(x) для всех достаточно больших значений x.
В случае сортировки методом вставки, когда мы рассматриваем выражение для максимального количества шагов, необходимых для выполнения алгоритма, выясняется, что оно является суммой двух слагаемых: одно кратно n2, а другое — n. Как упоминалось выше, слагаемое, кратное n, становится все менее значимым с ростом n, слагаемое n2 станет единственным, которое будет на что-то влиять. Таким образом, в худшем случае сортировка методом вставки имеет сложность O(n2) («находится в зависимости “O большое” от n2»).
Погоня за эффективностью алгоритмов состоит из поиска алгоритмов, время выполнения которых находится в зависимости «O большое» от все меньших функций. Если вам удастся найти возможность изменить сортировку методом вставки так, что она выполняется со сложностью O(n1,5) вместо O(n2), то это станет огромным достижением, которое очень сильно отразится на времени выполнения при больших значениях n. Нотация «O большое» может использоваться для оценки не только времени, но и затрат памяти. Некоторые алгоритмы могут добиться повышения скорости за счет хранения больших объемов данных в памяти. Их время выполнения может находиться в зависимости «O большое» от малой функции, тогда как затраты памяти будут находиться в зависимости «O большое» от большой функции. В зависимости от обстоятельств может быть разумным увеличить скорость за счет повышения затрат памяти или освободить память за счет некоторого снижения скорости. В этой главе мы сосредоточимся на достижении скорости и проектировании алгоритмов со временем выполнения, находящихся в отношении «О большое» с наименьшими возможными функциями без учета затрат памяти.
После того как вы узнали, что сортировка методом вставки обладает временем выполнения O(n2), естественно спросить: на какой уровень улучшения можно надеяться? Удастся ли найти какой-нибудь сверхъестественный алгоритм, который сможет отсортировать любой возможный список менее чем за десять шагов? Нет. Любому алгоритму сортировки потребуется не менее
