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

• При помощи методов динамического программирования (см. главу 9) можно создать алгоритм для игры в шашки.

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

Что вы узнаете об эффективности алгоритмов

А теперь хорошая новость: скорее всего, реализация каждого алгоритма в этой книге уже доступна на вашем любимом языке программирования и вам не придется писать каждый алгоритм самостоятельно! Но любая реализация будет бесполезной, если вы не понимаете ее плюсов и минусов. В этой книге вы научитесь сравнивать сильные и слабые стороны разных алгоритмов: из каких соображений выбирать между сортировкой слиянием и быстрой сортировкой? Что использовать — массив или список? Даже выбор другой структуры данных может оказать сильное влияние на результат.

Что вы узнаете о решении задач

Вы освоите методы решения задач, которые вам сейчас, возможно, неизвестны. Примеры:

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

• Вы узнаете, как построить рекомендательную систему на базе k ближайших соседей.

• Некоторые проблемы не решаются за разумное время! В части книги, посвященной NP-полноте задач, рассказано о том, как идентифицировать такие задачи и построить алгоритм для получения приближенного ответа.

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

Что необходимо знать

Чтобы читать эту книгу, необходимо знать базовую алгебру. Например, возьмем следующую функцию: f (x) = x × 2. Чему равен результат f(5)? Если вы ответили «10» — читайте спокойно.

Кроме того, вам будет проще понять эту главу (и всю книгу), если вы владеете хотя бы одним языком программирования. Все приведенные примеры написаны на Python. Если вы не знаете ни одного языка программирования, но хотите изучить — выбирайте Python: это отличный язык для начинающих. Если вы уже знаете другой язык (скажем, Ruby) — все в порядке.

Бинарный поиск

Предположим, вы ищете фамилию человека в телефонной книге (какая древняя технология!). Она начинается с буквы «К». Конечно, можно начать с самого начала и перелистывать страницы, пока вы не доберетесь до буквы «К». Но скорее всего для ускорения поиска лучше раскрыть книгу на середине: ведь буква «К» должна находиться где-то ближе к середине телефонной книги.

Или предположим, что вы ищете слово в словаре, и оно начинается с буквы «О». И снова лучше начать с середины.

Теперь допустим, что вы вводите свои данные при входе на Facebook. При этом Facebook необходимо проверить, есть ли у вас учетная запись на сайте. Для этого ваше имя пользователя нужно найти в базе данных. Допустим, вы выбрали себе имя пользователя «karlmageddon». Facebook может начать с буквы A и проверять все подряд, но разумнее будет начать с середины.

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

Бинарный поиск — это алгоритм; на входе он получает отсортированный список элементов (позднее я объясню, почему он должен быть отсортирован). Если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает null.

Например:

Ищем компанию в телефонной книге с применением бинарного поиска

Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.

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

Предположим, вы начинаете перебирать все варианты подряд: 1, 2, 3, 4 …. Вот как это будет выглядеть.

Плохой способ угадать число

Это пример простого поиска (возможно, термин «тупой поиск» был бы уместнее). При каждой догадке исключается только одно число. Если я загадал число 99, то, чтобы добраться до него, потребуется 99 попыток!

Более эффективный поиск

Существует другой, более эффективный способ. Начнем с 50.

Слишком мало… но вы только что исключили половину чисел! Теперь вы знаете, что все числа 1–50 меньше загаданного. Следующая попытка: 75.

На этот раз перелет… Но вы снова исключили половину оставшихся чисел! С бинарным поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел. Следующим будет число 63 (по середине между 50 и 75).

Так работает бинарный поиск. А вы только что узнали свой первый алгоритм! Попробуем поточнее определить, сколько чисел будет исключаться каждый раз.

При бинарном поиске каждый раз исключается половина чисел

Какое бы число я ни задумал, вы гарантированно сможете угадать его не более чем за 7 попыток, потому что с каждой попыткой исключается половина оставшихся чисел!

Предположим, вы ищете слово в словаре с 240 000 словами. Как вы думаете, сколько попыток вам понадобится в худшем случае?