айти алгоритмическое решение. А может, вы хотите понять, где вам могут пригодиться алгоритмы. Ниже приведен короткий и неполный список людей, которым может пригодиться книга:
• программисты-самоучки;
• студенты, начавшие изучать программирование;
• выпускники, желающие освежить память;
• специалисты по физике/математике/другим дисциплинам, интересующиеся программированием.
Условные обозначения и загружаемые материалы
Во всех примерах в книге используется Python 2.7. Весь программный код оформлен моноширинным шрифтом, чтобы его можно было отличить от обычного текста. Некоторые листинги сопровождаются аннотациями, подчеркивающими важные концепции.
Код примеров книги можно загрузить на сайте издательства по адресу www.manning.com/books/grokking-algorithms или https://github.com/egonschiele/grokking_algorithms.
Я считаю, что мы лучше всего учимся тогда, когда нам это нравится, — так что получайте удовольствие от процесса… и запускайте примеры кода!
Об авторе
Адитья Бхаргава работает программистом в Etsy, интернет-рынке авторских работ. Он получил степень магистра по информатике в Чикагском университете и ведет популярный иллюстрированный технический блог adit.io.
От издательства
Ваши замечания, предложения, вопросы отправляйте по адресу comp@piter.com (издательство «Питер», компьютерная редакция).
Мы будем рады узнать ваше мнение!
На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.
1. Знакомство с алгоритмами
В этой главе
• Закладываются основы для остальных глав книги.
• Вы напишете свой первый алгоритм поиска (бинарный поиск).
• Вы узнаете, как описывается время выполнения алгоритма («O-большое»).
• Будет представлен стандартный прием, часто применяемый при проектировании алгоритмов (рекурсия).
Введение
Алгоритмом называется набор инструкций для выполнения некоторой задачи. В принципе, любой фрагмент программного кода можно назвать алгоритмом, но в этой книге рассматриваются более интересные темы. Когда я отбирал алгоритмы для этой книги, я следил за тем, чтобы они были быстрыми или решали интересные задачи… или и то и другое сразу. Вот лишь несколько примеров.
• В главе 1 речь пойдет о бинарном поиске и о том, как алгоритмы могут ускорить работу кода. В одном примере алгоритм сокращает количество необходимых действий с 4 миллиардов до 32!
• Устройство GPS использует алгоритмы из теории графов (об этом в главах 6, 7 и 8) для вычисления кратчайшего пути к точке назначения.
• При помощи методов динамического программирования (см. главу 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 словами. Как вы думаете, сколько попыток вам понадобится в худшем случае?
При простом поиске может потребоваться 240 000 попыток, если искомое слово находится на самой последней позиции в книге. С каждым шагом бинарного поиска количество слов сокращается вдвое, пока не останется только одно слово.
Итак, бинарный поиск потребует 18 шагов — заметная разница! В общем случае для списка из n элементов бинарный поиск выполняется за log2n шагов, тогда как простой поиск будет выполнен за n шагов.
Логарифмы
Возможно, вы уже забыли, что такое логарифм, но наверняка помните, что такое возведение в степень. log10100 по сути означает, сколько раз нужно перемножить 10, чтобы получить 100. Правильный ответ — 2: 10 × 10. Итак, log10 100 = 2. Логарифм по смыслу противоположен возведению в степень.
Логарифм — операция, обратная возведению в степень
Когда я в этой книге упоминаю «O-большое» (об этом чуть позднее), log всегда означает log2. Когда вы ищете элемент с применением простого поиска, в худшем случае вам придется проверить каждый элемент. Итак, для списка из 8 чисел понадобится не больше 8 проверок. Для бинарного поиска в худшем случае потребуется не более logn проверок. Для списка из 8 элементов log 8 == 3, потому что 23 == 8. Итак, для списка из 8 чисел вам придется проверить не более 3 чисел. Для списка из 1024 элементов log 1024 = 10, потому что 210 == 1024. Следовательно, для списка из 1024 чисел придется проверить не более 10 чисел.
примечание
Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдет, если имена не будут отсортированы?