Мы увидели, как можно выражать временную сложность с помощью нотации «О большое» (O). На протяжении всей книги мы будем использовать ее, выполняя простой анализ временной сложности алгоритмов. Во многих случаях нет необходимости вычислять T(n), чтобы определить сложность алгоритма по «O большому». В следующей главе мы увидим более простые способы расчета сложности.
Еще мы увидели, что стоимость выполнения экспоненциальных алгоритмов имеет взрывной рост и делает их непригодными для входных данных большого объема. И мы узнали, как отвечать на вопросы:
• Насколько отличаются алгоритмы по числу требуемых для их выполнения операций?
• Как меняется время, необходимое алгоритму, при умножении объема входных данных на некую константу?
• Будет ли алгоритм по-прежнему выполнять приемлемое количество операций в случае, если вырастет объем входных данных?
• Если алгоритм выполняется слишком медленно для входных данных определенного объема, поможет ли его оптимизация или использование суперкомпьютера?
В следующей главе мы сосредоточимся на том, как связаны стратегии, лежащие в основе дизайна алгоритмов, с их временной сложностью.
Полезные материалы
• Кнут Д. Искусство программирования. Т. 1 (The Art of Computer Programming, см. https://code.energy/knuth).
• Зоопарк вычислительной сложности (The Computational Complexity Zoo, hackerdashery, см. https://code.energy/pnp).
Глава 3. Стратегия
Если видишь хороший ход — ищи ход получше.
В историю входят те полководцы, что достигали выдающихся результатов с помощью надежной стратегии. Чтобы успешно решать задачи, необходимо быть хорошим стратегом. Эта глава посвящена основным стратегиям, использующимся при проектировании алгоритмов. Вы узнаете:
как справляться с повторяющимися задачами посредством итераций;
как изящно выполнять итерации при помощи рекурсии;
как использовать полный перебор;
как выполнять проверку неподходящих вариантов и возвращаться на шаг назад;
как экономить время при помощи эвристических алгоритмов, помогающих найти разумный выход;
как применять принцип «Разделяй и властвуй» к самым неподатливыми противникам;
как динамически идентифицировать уже решенные задачи, чтобы снова не тратить на них энергию;
как ограничивать рамки задачи.
Вам предстоит познакомиться с множеством инструментов, но не переживайте — мы начнем с простых задач, а затем по мере изучения новых методов постепенно будем находить все лучшие решения. Достаточно скоро вы научитесь просто и изящно справляться с вычислительными задачами.
3.1. Итерация
Итеративная стратегия состоит в использовании циклов (например, for и while) для повторения процесса до тех пор, пока не окажется соблюдено некое условие. Каждый шаг в цикле называется итерацией. Итерации очень полезны для пошагового просмотра входных данных и применения одних и тех же операций к каждой их порции. Вот пример.
Объединение списков рыб 
У вас есть списки морских и пресноводных рыб, оба упорядочены в алфавитном порядке. Как создать из них один общий список, тоже отсортированный по алфавиту?
Мы можем сравнивать в цикле верхние элементы двух списков (рис. 3.1).
Данный процесс можно записать в виде одного цикла с условием продолжения while loop:
function merge(sea, fresh)
····result ← List.new
····while not (sea.empty and fresh.empty)
········if sea.top_item > fresh.top_item
············fish ← sea.remove_top_item
·······else
···········fish ← fresh.remove_top_item
·····result.append(fish)
return result
Рис. 3.1. Объединение двух отсортированных списков в третий, тоже отсортированный