рамки задачи.
Вам предстоит познакомиться с множеством инструментов, но не переживайте — мы начнем с простых задач, а затем по мере изучения новых методов постепенно будем находить все лучшие решения. Достаточно скоро вы научитесь просто и изящно справляться с вычислительными задачами.
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. Объединение двух отсортированных списков в третий, тоже отсортированный
Он выполняет обход всех названий рыб из входных списков, совершая фиксированное число операций для каждого элемента[28]. Следовательно, алгоритм слияния merge имеет сложность O(n).
Вложенные циклы и степенные множества
В предыдущей главе мы увидели, как функция сортировки выбором selection_sort использует один цикл, вложенный в другой. Сейчас мы научимся использовать вложенный цикл для вычисления степенного множества. Если дана коллекция объектов S, то степенное множество S есть множество, содержащее все подмножества S[29].
Исследование запахов В парфюмерии цветочные ароматы изготавливают путем комбинирования запахов различных цветов. Если дано множество цветов F, то как посчитать все ароматы, которые можно изготовить из них?
Любой аромат состоит из подмножества F, потому его степенное множество содержит все возможные ароматы. Это степенное множество вычисляется итеративно. Для нулевого множества цветов есть всего один вариант — без запаха. В случае, когда мы берем очередной цветок, мы дублируем уже имеющиеся ароматы и добавляем его к ним (рис. 3.2).
Этот процесс можно описать при помощи циклов. Во внешнем цикле мы принимаем решение, какой цветок будем рассматривать следующим. Внутренний цикл дублирует ароматы и добавляет новый цветок к этим копиям.
function power_set(flowers)····fragrances ← Set.new····fragrances.add(Set.new)····for each flower in flowers········new_fragrances ← copy(fragrances)········for each fragrance in new_fragrances············fragrance.add(flower)········fragrances ← fragrances + new_fragrances····return fragrancesДобавление каждого нового цветка приводит к удвоению количества ароматов в множестве fragrances, что говорит об экспоненциальном росте (2k+1 = 2 × 2k). Алгоритмы, которые удваивают число операций, если объем входных данных увеличивается на один элемент, — экспоненциальные, их временная сложность — O(2n).
Генерирование степенных множеств эквивалентно генерированию таблиц истинности (см. раздел «Логика» в главе 1). Если обозначить каждый цветок логической переменной, то любой аромат легко представить в виде значений True/False этих переменных. В таблице истинности каждая строка будет возможной формулой аромата.
Рис. 3.2. Итеративное перечисление всех ароматов с использованием четырех цветков
3.2. Рекурсия
Мы говорим о рекурсии, когда функция делегирует работу своим клонам. Рекурсивный алгоритм естественным образом приходит на ум, когда нужно решить задачу, сформулированную с точки зрения самой себя. Например, возьмем известную последовательность Фибоначчи. Она начинается с двух единиц, и каждое последующее число является суммой двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21. Как создать функцию, возвращающую n-е число Фибоначчи (рис. 3.3)?
Рис. 3.3. Рекурсивное вычисление шестого числа Фибоначчи
function fib(n)····if n ≤ 2········return 1····return fib(n — 1) + fib(n — 2)При использовании рекурсии требуется творческий подход, чтобы понять, каким образом задача может быть поставлена с точки зрения самой себя. Чтобы проверить, является ли слово палиндромом[30], нужно посмотреть, изменится ли оно, если его перевернуть. Это можно сделать, проверив, одинаковы ли первая и последняя буквы слова и не является ли палиндромом заключенная между ними часть слова (рис. 3.4).
Рис. 3.4. Рекурсивная проверка, является ли слово racecar палиндромом
function palindrome(word)····if word.length ≤ 1········return True····if word.first_char ≠ word.last_char········return False····w ← word.remove_first_and_last_chars····return palindrome(w)Рекурсивные алгоритмы имеют базовые случаи, когда объем входных данных слишком мал, чтобы его можно было продолжать сокращать. Базовые случаи для функции fib — числа 1 и 2; для функции palindrome это слова, состоящие из единственной буквы или не имеющие ни одной буквы.
Рекурсия против итераций
Рекурсивные алгоритмы обычно проще и короче итеративных. Сравните эту рекурсивную функцию с power_set из предыдущего раздела, которая не использует рекурсию:
function recursive_power_set(items)····ps ← copy(items)····for each e in items·······ps ← ps.remove(e)·······ps ← ps + recursive_power_set(ps)·······ps ← ps.add(e)····return psЭта простота имеет свою цену. Рекурсивные алгоритмы при выполнении порождают многочисленные копии самих себя, создавая дополнительные вычислительные издержки. Компьютер должен отслеживать незаконченные рекурсивные вызовы и их частичные вычисления, что требует большего объема памяти. При этом дополнительные такты центрального процессора расходуются на переключение с одного рекурсивного вызова на следующий и назад.
Эту проблему можно наглядно увидеть на деревьях рекурсивных вызовов — диаграммах, показывающих, каким образом алгоритм порождает новые вызовы, углубляясь в вычисления. Мы уже видели деревья рекурсивных вызовов для поиска чисел Фибоначчи (см. рис. 3.3) и для проверки слов-перевертышей (см. рис. 3.4).
Если требуется максимальная производительность, то можно избежать этих дополнительных издержек, переписав рекурсивный алгоритм в чисто итеративной форме. Такая возможность есть всегда. Это компромисс: итеративный программный код обычно выполняется быстрее, но вместе с тем он более громоздкий и его труднее понять.
3.3. Полный перебор
Полный перебор, он же метод «грубой силы», предполагает перебор всех случаев, которые могут быть решением задачи. Эта стратегия также называется исчерпывающим поиском. Она обычно прямолинейна и незамысловата: даже в том случае, когда вариантов миллиарды, она все равно опирается исключительно на силу, то есть на способность компьютера проверить их все.
Рис. 3.5. Простое объяснение: полный перебор[31]
Давайте посмотрим, как ее можно использовать, чтобы решить следующую задачу.
Лучшая сделка У вас есть список цен на золото по дням за какой-то интервал времени. В этом интервале вы хотите найти такие два дня, чтобы, купив золото, а затем продав его, вы получили бы максимально возможную прибыль.
Не всегда у вас получится сделать покупку по самой низкой цене, а продать по самой высокой: первая может случиться позже второй, а перемещаться во времени вы не умеете. Алгоритм полного перебора позволяет просмотреть все пары дней. По каждой паре он находит прибыль и сравнивает ее с наибольшей, найденной к этому моменту. Мы знаем, что число пар дней в интервале растет квадратично по мере его увеличения[32]. Еще не приступив к написанию кода, мы уже уверены, что он будет иметь O(n2).
Задача о лучшей сделке решается и с помощью других стратегий с меньшей временной сложностью — мы вскоре их рассмотрим. Но в некоторых случаях наилучшую временную сложность дает подход на основе полного перебора. Это имеет место в следующей задаче.