Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих

«Разделяй и властвуй»

Возможно, вы не сразу поймете суть стратегии «разделяй и властвуй», поэтому мы рассмотрим три примера. Сначала я приведу наглядный пример. Потом мы разберем пример кода, который выглядит не так красиво, но, пожалуй, воспринимается проще. В завершение будет рассмотрена быстрая сортировка — алгоритм сортировки, использующий стратегию «разделяй и властвуй».

Представьте, что вы фермер, владеющий земельным участком.

Вы хотите равномерно разделить землю на одинаковые квадратные участки. Участки должны быть настолько большими, насколько это возможно, так что ни одно из следующих решений не подойдет.

Как определить наибольший размер квадрата для участка? Воспользуйтесь стратегией «разделяй и властвуй»! Алгоритмы на базе этой стратегии являются рекурсивными.

Решение задачи методом «разделяй и властвуй» состоит из двух шагов:

1. Сначала определяется базовый случай. Это должен быть простейший случай из всех возможных.

2. Задача делится или сокращается до тех пор, пока не будет сведена к базовому случаю.

А теперь воспользуемся стратегией «разделяй и властвуй» для поиска решения этой задачи. Каков самый большой размер квадрата, который может использоваться?

Для начала нужно определить базовый случай. Самая простая ситуация — если длина одной стороны кратна длине другой стороны.

Предположим, длина одной стороны составляет 25 м, а длина другой 50 м. В этом случае размер самого большого участка составляет 25 м × 25 м, и надел после деления будет состоять из двух участков.

Теперь нужно вычислить рекурсивный случай. Здесь-то вам на помощь и приходит стратегия «разделяй и властвуй». В соответствии с ней при каждом рекурсивном вызове задача должна сокращаться. Как сократить эту задачу? Для начала разметим самые большие участки, которые можно использовать.

В исходном наделе можно разместить два участка 640 × 640, и еще останется место. Тут-то и наступает момент истины. Нераспределенный остаток — это тоже надел земли, который нужно разделить. Так почему бы не применить к нему тот же алгоритм?

Итак, мы начали с надела 1680 × 640, который необходимо разделить на участки. Но теперь разделить нужно меньший сегмент — 640 × 400. Если вы найдете самый большой участок, подходящий для этого размера, это будет самый большой участок, подходящий для всей фермы. Мы только что сократили задачу с размера 1680 × 640 до 640 × 400!

Алгоритм Евклида

«Если вы найдете самый большой участок, подходящий для этого размера, это будет самый большой участок, подходящий для всей фермы». Если истинность этого утверждения для вас неочевидна, не огорчайтесь. Она действительно не очевидна. К сожалению, доказательство получится слишком длинным, чтобы его можно было бы привести в книге, поэтому вам придется просто поверить мне на слово. Если вас интересует доказательство, поищите «алгоритм Евклида». Хорошее объяснение содержится на сайте Khan Academy: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm.

Применим тот же алгоритм снова. Если начать с участка 640 × 400, то размеры самого большого квадрата, который можно создать, составляют 400 × 400 м.

Остается меньший сегмент с размерами 400 × 240 м.

Отсекая поделенную часть, мы приходим к еще меньшему размеру сегмента, 240 × 160 м.

После очередного отсечения получается еще меньший сегмент.

Эге, да мы пришли к базовому случаю: 160 кратно 80. Если разбить этот сегмент на квадраты, ничего лишнего не останется!

Итак, для исходного надела земли самый большой размер участка будет равен 80 × 80 м.

Вспомните, как работает стратегия «разделяй и властвуй»:

1. Определите простейший случай как базовый.

2. Придумайте, как свести задачу к базовому случаю.

«Разделяй и властвуй» — не простой алгоритм, который можно применить для решения задачи. Скорее, это подход к решению задачи. Рассмотрим еще один пример.

Имеется массив чисел.

Нужно просуммировать все числа и вернуть сумму. Сделать это в цикле совсем не сложно:

def sum(arr):

total = 0

for x in arr:

total += x

return total

print sum([1, 2, 3, 4])

Но как сделать то же самое c использованием рекурсивной функции?

Шаг 1: определить базовый случай. Как выглядит самый простой массив, который вы можете получить? Подумайте, как должен выглядеть простейший случай, и продолжайте читать. Если у вас будет массив с 0 или 1 элементом, он суммируется достаточно просто.

Итак, с базовым случаем мы определились.

Шаг 2: каждый рекурсивный вызов должен приближать вас к пустому массиву. Как уменьшить размер задачи? Один из возможных способов:

В любом случае результат равен 12. Но во второй версии функции sum передается меньший массив. А это означает, что вы сократили размер своей задачи!

Функция sum может работать по следующей схеме:

А вот как это выглядит в действии.

Вспомните, что при рекурсии сохраняется состояние.

совет

Когда вы пишете рекурсивную функцию, в которой задействован массив, базовым случаем часто оказывается пустой массив или массив из одного элемента. Если вы не знаете, с чего начать, — начните с этого.

Пара слов о функциональном программировании

Зачем применять рекурсию, если задача легко решается с циклом? Вполне резонный вопрос. Что ж, пора познакомиться с функциональным программированием!

В языках функционального программирования, таких как Haskell, циклов нет, поэтому для написания подобных функций приходится применять рекурсию. Если вы хорошо понимаете рекурсию, вам будет проще изучать функциональные языки. Например, вот как выглядит функция sum на языке Haskell:

sum [] = 0 Базовый случай

sum (x:xs) = x + (sum xs) Рекурсивный случай

На первый взгляд кажется, что одна функция имеет два определения. Первое определение выполняется для базового случая, а второе — для рекурсивного случая. Функцию также можно записать на Haskell с использованием команды if:

sum arr = if arr == []

then 0

else (head arr) + (sum (tail arr))

Но первое определение проще читается. Так как рекурсия широко применяется в языке Haskell, в него включены всевозможные удобства для ее использования. Если вам нравится рекурсия или вы хотите изучить новый язык — присмотритесь к Haskell.

Упражнения

4.1 Напишите код для функции sum (см. выше).

4.2 Напишите рекурсивную функцию для подсчета элементов в списке.

4.3 Найдите наибольшее число в списке.

4.4 Помните бинарный поиск из главы 1? Он тоже относится к классу алгоритмов «разделяй и властвуй». Сможете ли вы определить базовый и рекурсивный случай для бинарного поиска?

Быстрая сортировка

Быстрая сортировка относится к алгоритмам сортировки. Она работает намного быстрее сортировки выбором и часто применяется в реальных программах. Например, в стандартную библиотеку C входит функция с именем qsort, реализующая быструю сортировку. Быстрая сортировка также основана на стратегии «разделяй и властвуй».

Воспользуемся быстрой сортировкой для упорядочения массива. Как выглядит самый простой массив, с которым может справиться алгоритм сортировки (помните подсказку из предыдущего раздела)? Некоторые массивы вообще не нуждаются в сортировке.

Пустые массивы и массивы, содержащие всего один элемент, станут базовым случаем. Такие массивы можно просто возвращать в исходном виде — сортировать ничего не нужно:

def quick sor t(array):

if len(array) < 2:

return array

Теперь перейдем к массивам большего размера. Массив из двух элементов тоже сортируется без особых проблем.

А как насчет массива из трех элементов?

Помните: мы используем стратегию «разделяй и властвуй». Следовательно, массив должен разделяться до тех пор, пока мы не придем к базовому случаю. Алгоритм быстрой сортировки работает так: сначала в массиве выбирается элемент, который называется опорным.

О том, как выбрать хороший опорный элемент, будет рассказано далее. А пока предположим, что опорным становится первый элемент массива.

Теперь мы находим элементы, меньшие опорного, и элементы, большие опорного.

Этот процесс называется разделением. Теперь у вас имеются:

• подмассив всех элементов, меньших опорного;

• опорный элемент;

• подмассив всех элементов, больших опорного.

Два подмассива не отсортированы — они просто выделены из исходного массива. Но если бы они были отсортированы, то провести сортировку всего массива было бы несложно.

Если бы подмассивы были отсортированы, то их можно было бы объединить в порядке «левый подмассив — опорный элемент — правый подмассив» и получить отсортированный массив. В нашем примере получается [10, 15] + [33] + [] = [10, 15, 33], то есть отсортированный массив.

Как отсортировать подмассивы? Базовый случай быстрой сортировки уже знает, как сортировать массивы из двух элементов (левый подмассив) и пустые массивы (правый подмассив). Следовательно, если применить алгоритм быстрой сортировки к двум подмассивам, а затем объединить результаты, получится отсортированный массив!

quicksort([15, 10]) + [33] + quicksort([])

> [10, 15, 33] Отсортированный массив

Этот метод работает при любом опорном элементе. Допустим, вместо 33 в качестве опорного был выбран элемент 15.

Оба подмассива состоят из одного элемента, а вы уже умеете сортировать такие подмассивы. Получается, что вы умеете сортировать массивы из трех элементов. Это делается так:

1. Выбрать опорный элемент.

2. Разделить массив на два подмассива: элементы, меньшие опорного, и элементы, большие опорного.

3. Рекурсивно применить быструю сортировку к двум подмассивам.

Как насчет массива из четырех элементов?

Предположим, опорным снова выбирается элемент 33.

Левый подмассив состоит из трех элементов. Вы уже знаете, как сортируется массив из трех элементов: нужно рекурсивно применить к нему быструю сортировку.

Следовательно, вы можете отсортировать массив из четырех элементов. А если вы можете отсортировать массив из четырех элементов, то вы также можете отсортировать массив из пяти элементов. Почему? Допустим, имеется массив из пяти элементов.

Вот как выглядят все варианты разделения этого массива в зависимости от выбранного опорного элемента:

Все эти подмассивы содержат от 0 до 4 элементов. А вы уже знаете, как отсортировать массив, содержащий от 0 до 4 элементов, с использованием быстрой сортировки! Таким образом, независимо от выбора опорного элемента вы можете рекурсивно вызывать быструю сортировку для двух подмассивов.

Например, предположим, что в качестве опорного выбирается элемент 3. Вы применяете быструю сортировку к подмассивам.

Подмассивы отсортированы, и теперь из них можно собрать отсортированный массив. Решение работает даже в том случае, если выбрать в качестве опорного элемент 5:

Итак, решение работает независимо от выбора опорного элемента. Следовательно, вы можете отсортировать массив из пяти элементов. По той же логике вы можете отсортировать массив из шести элементов и т.д.

доказательство по индукции

Вы только что познакомились с методом доказательства по индукции! Это один из способов, доказывающих, что ваш алгоритм работает. Каждое индуктивное доказательство состоит из двух частей: базы (базового случая) и индукционного перехода. Звучит знакомо? Допустим, я хочу доказать, что могу подняться на самый верх стремянки. Если мои ноги стоят на ступеньке, то я могу переставить их на следующую ступеньку, — это индукционный переход. Таким образом, если я стою на ступеньке 2, то могу подняться на ступеньку 3. Что касается базового случая, я сейчас стою на ступеньке 1. Из этого следует, что я могу подняться на самый верх стремянки, каждый раз поднимаясь на одну ступеньку.

Аналогичные рассуждения применимы к быстрой сортировке. Работоспособность алгоритма для базового случая — массивов с размером 0 и 1 — была продемонстрирована. В индукционном переходе я показал, что если быстрая сортировка работает для массива из 1 элемента, то она будет работать для массива из 2 элементов. А если она работает для массивов из 2 элементов, то она будет работать для массивов из 3 элементов и т.д. Из этого можно сделать вывод, что быстрая сортировка будет работать для всех массивов любого размера. Я не буду подробно рассматривать доказательства по индукции, но это интересный метод, который идет рука об руку со стратегией «разделяй и властвуй».

А вот как выглядит программный код быстрой сортировки:

def quicksort(array):

if len(array) < 2:

return array Базовый случай: массивы с 0 и 1 элементом уже "отсортированы"

else:

pivot = array[0] Рекурсивный случай

less = [i for i in array[1:] if i < pivot] Подмассив всех элементов, меньших опорного

greater = [i for i in array[1:] if i > pivot] Подмассив всех элементов, больших опорного

return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])

Снова об «O-большом»

Алгоритм быстрой сортировки уникален тем, что его скорость зависит от выбора опорного элемента. Прежде чем рассматривать быструю сортировку, вспомним наиболее типичные варианты времени выполнения для «O-большое».

Оценки для медленного компьютера, выполняющего 10 операций в секунду

На графиках приведены примерные оценки времени при выполнении 10 операций в секунду. Они не претендуют на точность, а всего лишь дают представление о том, насколько различается время выполнения. Конечно, на практике ваш компьютер способен выполнять гораздо больше 10 операций в секунду.

Для каждого времени выполнения также приведен пример алгоритма. Возьмем алгоритм сортировки выбором, о котором вы узнали в главе 2. Он обладает временем O(n2), и это довольно медленный алгоритм.

Другой алгоритм сортировки — так называемая сортировка слиянием — работает за время O(n log n). Намного быстрее! С быстрой сортировкой дело обстоит сложнее. В худшем случае быстрая сортировка работает за время O(n2).

Ничуть не лучше сортировки выбором! Но это худший случай, а в среднем быстрая сортировка выполняется за время O(n log n). Вероятно, вы спросите:

• что в данном случае понимается под «худшим» и «средним» случаем?

• если быстрая сортировка в среднем выполняется за время O(n log n), а сортировка слиянием выполняется за время O(n log n) всегда, то почему бы не использовать сортировку слиянием? Разве она не быстрее?

Сортировка слиянием и быстрая сортировка

Допустим, у вас имеется простая функция для вывода каждого элемента в списке:

def print_items(list):

for item in list:

print item

Эта функция последовательно перебирает все элементы списка и выводит их. Так как функция перебирает весь список, она выполняется за время O(n). Теперь предположим, что вы изменили эту функцию и она делает секундную паузу перед выводом:

from time import sleep

def print_items2(list):

for item in list:

sleep(1)

print item

Перед выводом элемента функция делает паузу продолжительностью в 1 секунду. Предположим, вы выводите список из пяти элементов с использованием обеих функций:

Обе функции проходят по списку один раз, и обе выполняются за время O(n). Как вы думаете, какая из них работает быстрее? Я думаю, print_items работает намного быстрее, потому что она не делает паузу перед выводом каждого элемента. Следовательно, даже при том, что обе функции имеют одинаковую скорость «O-большое», реально print_items работает быстрее. Когда вы используете «O-большое» (например, O(n)), в действительности это означает следующее:

Здесь c — некоторый фиксированный промежуток времени для вашего алгоритма. Он называется константой. Например, время выполнения может составлять 10 миллисекунд * n для print_items против 1 секунды * n для print_items2.

Обычно константа игнорируется, потому что если два алгоритма имеют разное время «O-большое», она роли не играет. Для примера возьмем бинарный и простой поиск. Допустим, такие константы присутствуют в обоих алгоритмах.

Первая реакция: «Ого! У простого поиска константа равна 10 миллисекундам, а у бинарного поиска – 1 секунда. Простой поиск намного быстрее!» Теперь предположим, что поиск ведется по списку из 4 миллиардов элементов. Время будет таким:

Как видите, бинарный поиск все равно работает намного быстрее. Константа ни на что не повлияла.

Однако в некоторых случаях константа может иметь значение. Один из примеров такого рода — быстрая сортировка и сортировка слиянием. У быстрой сортировки константа меньше, чем у сортировки слиянием, поэтому, несмотря на то что оба алгоритма характеризуются временем O(n log n), быстрая сортировка работает быстрее. А на практике быстрая сортировка работает быстрее, потому что средний случай встречается намного чаще худшего.

А теперь ответим на первый вопрос: как выглядит средний случай по сравнению с худшим?

Средний и худший случай

Быстродействие быстрой сортировки сильно зависит от выбора опорного элемента. Предположим, опорным всегда выбирается первый элемент, а быстрая сортировка применяется к уже отсортированному массиву. Быстрая сортировка не проверяет, отсортирован входной массив или нет, и все равно пытается его отсортировать.

Обратите внимание: на этот раз массив не разделяется на две половины. Вместо этого один из двух подмассивов всегда пуст, так что стек вызовов получается очень длинным. Теперь предположим, что в качестве опорного всегда выбирается средний элемент. Посмотрим, как выглядит стек вызовов в этом случае.

Стек намного короче! Массив каждый раз делится надвое, поэтому такое количество рекурсивных вызовов излишне. Вы быстрее добираетесь до базового случая, и стек вызовов получается более коротким.

Первый из рассмотренных примеров описывает худший сценарий, а второй — лучший. В худшем случае размер стека описывается как O(n). В лучшем случае он составит O(log n).

Теперь рассмотрим первый уровень стека. Один элемент выбирается опорным, а остальные элементы делятся на подмассивы. Вы перебираете все восемь элементов массива, поэтому первая операция выполняется за время O(n). На этом уровне стека вызовов вы обратились ко всем восьми элементам. Но на самом деле вы обращаетесь к O(n) элементам на каждом уровне стека вызовов!

Даже если массив будет разделен другим способом, вы все равно каждый раз обращаетесь к O(n) элементам.

Итак, завершение каждого уровня требует времени O(n).

В этом примере существуют O(log n) (с технической точки зрения правильнее сказать «высота стека вызовов равна O(log n)») уровней. А так как каждый уровень занимает время O(n), то весь алгоритм займет время O(n) * O(log n) = O(n log n). Это сценарий лучшего случая.

В худшем случае существуют O(n) уровней, поэтому алгоритм займет время O(n)* O(n) = O(n2).

А теперь сюрприз: лучший случай также является средним. Если вы всегда будете выбирать опорным элементом случайный элемент в массиве, быстрая сортировка в среднем завершится за время O(n log n). Это один из самых быстрых существующих алгоритмов сортировки, который заодно является хорошим примером стратегии «разделяй и властвуй».

Упражнения

Запишите «O-большое» для каждой из следующих операций ?

4.5 Вывод значения каждого элемента массива.

4.6 Удвоение значения каждого элемента массива.

4.7 Удвоение значения только первого элемента массива.

4.8 Создание таблицы умножения для всех элементов массива. Например, если массив состоит из элементов [2, 3, 7, 8, 10], сначала каждый элемент умножается на 2, затем каждый элемент умножается на 3, затем на 7 и т.д.

Шпаргалка

• Стратегия «разделяй и властвуй» основана на разбиении задачи на уменьшающиеся фрагменты. Если вы используете стратегию «разделяй и властвуй» со списком, то базовым случаем, скорее всего, является пустой массив или массив из одного элемента.

• Если вы реализуете алгоритм быстрой сортировки, выберите в качестве опорного случайный элемент. Среднее время выполнения быстрой сор­тировки составляет O(n log n)!

• Константы в «O-большом» иногда могут иметь значение. Именно по этой причине быстрая сортировка быстрее сортировки слиянием.

• При сравнении простой сортировки с бинарной константа почти никогда роли не играет, потому что O(log n) слишком сильно превосходит O(n) по скорости при большом размере списка.