2.4. Оценка затрат памяти
Даже если бы мы могли выполнять операции бесконечно быстро, мы все равно столкнулись бы с ограничениями. Алгоритмам во время их исполнения нужна рабочая область для хранения промежуточных результатов. Эта область занимает память компьютера, отнюдь не бесконечную.
Мера рабочей области хранения, в которой нуждается алгоритм, называется пространственной сложностью. Анализ пространственной сложности выполняется аналогично анализу временной сложности. Разница лишь в том, что мы ведем учет не вычислительных операций, а памяти компьютера. Мы наблюдаем за тем, как эволюционирует пространственная сложность с ростом объема входных данных, точно так же, как делаем это в случае временной сложности.
Например, для сортировки выбором (см. раздел «Оценка затрат времени») нужна рабочая область хранения для фиксированного набора переменных. Число переменных не зависит от объема входных данных. Поэтому мы говорим, что пространственная сложность сортировки выбором составляет O(1) — независимо от объема входных данных она требует одного объема памяти компьютера для рабочей области хранения.
Однако многие другие алгоритмы нуждаются в такой рабочей области хранения, которая растет вместе с объемом входных данных. Иногда бывает невозможно удовлетворить потребности алгоритма в памяти. Вы не найдете подходящий алгоритм сортировки с временной сложностью O(n log n) и пространственной сложностью O(1). Ограниченность памяти компьютера иногда вынуждает искать компромисс. В случае если доступно мало памяти, вам, вероятно, потребуется медленный алгоритм с временной сложностью, потому что он имеет пространственную сложность O(1). В последующих главах мы увидим, как разумно выстроенная обработка данных способна улучшить пространственную сложность.
Подведем итоги
Из этой главы нам стало известно, что алгоритмы могут проявлять различный уровень «жадности» по отношению к потреблению вычислительного времени и памяти компьютера. Мы узнали, каким образом это можно диагностировать при помощи анализа временной и пространственной сложности, и научились вычислять временную сложность путем нахождения точной функции T(n), то есть количества выполняемых алгоритмом операций.
Мы увидели, как можно выражать временную сложность с помощью нотации «О большое» (O). На протяжении всей книги мы будем использовать ее, выполняя простой анализ временной сложности алгоритмов. Во многих случаях нет необходимости вычислять T(n), чтобы определить сложность алгоритма по «O большому». В следующей главе мы увидим более простые способы расчета сложности.
Еще мы увидели, что стоимость выполнения экспоненциальных алгоритмов имеет взрывной рост и делает их непригодными для входных данных большого объема. И мы узнали, как отвечать на вопросы:
• Насколько отличаются алгоритмы по числу требуемых для их выполнения операций?
• Как меняется время, необходимое алгоритму, при умножении объема входных данных на некую константу?
• Будет ли алгоритм по-прежнему выполнять приемлемое количество операций в случае, если вырастет объем входных данных?
• Если алгоритм выполняется слишком медленно для входных данных определенного объема, поможет ли его оптимизация или использование суперкомпьютера?
В следующей главе мы сосредоточимся на том, как связаны стратегии, лежащие в основе дизайна алгоритмов, с их временной сложностью.
Полезные материалы
• Кнут Д. Искусство программирования. Т. 1 (The Art of Computer Programming, см. https://code.energy/knuth).
• Зоопарк вычислительной сложности (The Computational Complexity Zoo, hackerdashery, см. https://code.energy/pnp).
Глава 3. Стратегия
Если видишь хороший ход — ищи ход получше.
Эмануэль Ласкер
В историю входят те полководцы, что достигали выдающихся результатов с помощью надежной стратегии. Чтобы успешно решать задачи, необходимо быть хорошим стратегом. Эта глава посвящена основным стратегиям, использующимся при проектировании алгоритмов. Вы узнаете:
как справляться с повторяющимися задачами посредством итераций;
как изящно выполнять итерации при помощи рекурсии;
как использовать полный перебор;
как выполнять проверку неподходящих вариантов и возвращаться на шаг назад;
как экономить время при помощи эвристических алгоритмов, помогающих найти разумный выход;
как применять принцип «Разделяй и властвуй» к самым неподатливыми противникам;
как динамически идентифицировать уже решенные задачи, чтобы снова не тратить на них энергию;
как ограничивать рамки задачи.
