|
4
Знакомство с алгоритмами
В этой главе
Закладываются основы для остальных глав книги.
Вы напишете свой первый алгоритм поиска (бинарный поиск).
Вы узнаете, как описывается время выполнения алгоритма («О-большое»).
Будет представлен стандартный прием, часто применяемый при проектировании алгоритмов (рекурсия).
Введение
Алгоритмом называется набор инструкций для выполнения некоторой задачи. В принципе, любой фрагмент программного кода можно назвать алгоритмом, но в этой книге рассматриваются более интересные темы. Когда я отбирал алгоритмы для этой книги, я следил за тем, чтобы они были быстрыми или решали интересные задачи... или и то и другое сразу. Вот лишь несколько примеров.
В главе 1 речь пойдет о бинарном поиске и о том, как алгоритмы могут ускорить работу кода. В одном примере алгоритм сокращает количество необходимых действий с 4 миллиардов до 32!
Устройство GPS использует алгоритмы из теории графов (об этом в главах 6, 7 и 8) для вычисления кратчайшего пути к точке назначения.
При помощи методов динамического программирования (см. главу 9) можно создать алгоритм для игры в шашки.
В каждом случае я опишу алгоритм и приведу пример. Затем мы обсудим время выполнения алгоритма в понятиях «О-большое». В завершение будут рассмотрены типы задач, которые могут решаться с применением того же алгоритма.
Что вы узнаете об эффективности алгоритмов
А теперь хорошая новость: скорее всего, реализация каждого алгоритма в этой книге уже доступна на вашем любимом языке программирования и вам не придется писать каждый алгоритм самостоятельно! Но любая реализация будет бесполезной, если вы не понимаете ее плюсов и минусов. В этой книге вы научитесь сравнивать сильные и слабые стороны разных алгоритмов: из каких соображений выбирать между сортировкой слиянием и быстрой сортировкой? Что использовать — массив или список? Даже выбор другой структуры данных может оказать сильное влияние на результат.
Что вы узнаете о решении задач
Вы освоите методы решения задач, которые вам сейчас, возможно, неизвестны. Примеры:
Если вы любите создавать видеоигры, вы можете написать систему на базе искусственного интеллекта, моделирующую действия пользователя с применением алгоритмов из теории графов.
Вы узнаете, как построить рекомендательную систему на базе к ближайших соседей.
□ Некоторые проблемы не решаются за разумное время! В части книги, посвященной NP-полноте задач, рассказано о том, как идентифицировать такие задачи и построить алгоритм для получения приближенного ответа.
А если брать шире, к концу этой книги вы освоите некоторые широко применяемые алгоритмы. После этого вы сможете воспользоваться новыми знаниями для изучения более специализированных алгоритмов из области искусственного интеллекта, баз данных и т. д. или взяться за решение более сложных задач в практической работе.
Ч
■И
тт
Ary?
ТО НЕОБХОДИМО ЗНАТЬ
Чтобы читать эту книгу, необходимо знать базовую aj мер, возьмем следующую функцию: / (х) = х * 2. Чему равен результат /(5)? Если вы ответили «10» — читайте спокойно.
Кроме того, вам будет проще понять эту главу (и всю книгу), е владеете хотя бы одним языком программирования. Все . ные примеры написаны на Python. Если вы не знаете ни одного г ка программирования, но хотите изучить — выбирайте " ’ отличный язык для начинающих. Если вы уже знаете (скажем, Ruby) — все в порядке.
Б
инарный поиск
Предположим, вы ищете фамилию человека в телефонной книге (какая древняя технология!). Она начинается с буквы «К». Конечно, можно начать с самого начала и перелистывать страницы, пока вы не доберетесь до буквы «К». Но скорее всего для ускорения поиска лучше раскрыть книгу на середине: ведь буква «К» должна находиться где- то ближе к середине телефонной книги.
Или предположим, что вы ищете слово в словаре, и оно начинается с буквы «О». И снова лучше начать с середины.
Теперь допустим, что вы вводите свои данные при входе на Facebook. При этом Facebook необходимо проверить, есть ли у вас учетная запись на сайте. Для этого ваше имя пользователя нужно найти в базе данных. Допустим, вы выбрали себе имя пользователя «karlmageddon».
F
i
acebook может начать с буквы А и проверять все подряд, но разумнее будет начать с середины.
Перед нами типичная задача поиска. И во всех этих случаях для решения задачи можно применить один алгоритм: бинарный поиск.
Бинарный поиск — это алгоритм; на входе он получает отсортированный список элементов (позднее я объясню, почему он должен быть отсортирован). Если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает null.
Н
Do'stlaringiz bilan baham: |
