Практическая работа 2. Базовые сведения об алгоритмах

Зачем изучать алгоритмы? Для программиста существуют две причины: практическая и теоретическая. С практической точки зрения он должен иметь представление о стандартном наборе основных алгоритмов, относящихся к разным областям компьютерных наук. Кроме того, он должен ументь разрабатывать новые алгоритмы и анализировать их эффективность. С теоретической точки зрения процесс изучения алгоритмов, который иногда называют алгоритмикой (algorithmics), считается краеугольным камнем computer science.

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

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

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

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

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

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

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

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

Рассмотрим пример того, как работает бинарный поиск. Представьте себе, что вы играете с приятелем в игру "Угадай число от 1 до 100".

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

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

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

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

Начнем с 50. Если приятель говорит "мало", то мы исключаем половину чисел из всего диапазона (от 1 до 100). Теперь вы знаете, что все числа 1 - 50 меньше загаданного. Следующая попытка: 75.

Приятель говорит "много". Но мы снова исключаем половину оставшихся чисел (числа от 75 до 100 гарантированно будут больше, чем загаданное число).

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

Следующим будет число 63 (посередине между 50 и 75).

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

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

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

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

Итак, бинарный поиск потребует 18 шагов - заметная разница! В общем случае для списка из n элементов бинарный поиск выполняется за

$$log_2n$$

шагов, тогда как простой поиск будет выполняться за n шагов.

Логарфимы

Выражение

$$log_{10} 100$$

по сути ознчает, сколько раз нужно перемножить 10, чтобы получить 100. Правильный ответ равен 2: 10 * 10 = 100. Таким образом

$$log_{10} 100 = 2$$

Логарифм по смыслу противоположен возведению в степень.

$$10^2 = 100 \; ; \; log_{10}100 = 2 \\ 10^3 = 1000 \; ; \; log_{10}1000 = 3 \\ 2^3 = 8 \; ; \; log_{2}8= 3 \\ 2^4 = 16 \; ; \; log_{2}8= 4 \\ 2^5 = 32 \; ; \; log_{2}32 = 5 \\$$

Когда впредь будет упоминаться log, то это почти всегда означает логарифм по основанию 2.

Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдет, если имена не будут отсортированы?

Время выполнения

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

Сколько времени сэкономит применение бинарного поиска. В случае линейного поиска мы проверяли каждое число, одно за другим. Если список состоит из 100 элементов, может потребоваться до 100 попыток. Для списка из 4 миллиардов чисел потребуется до 4 миллиардов попыток. Таким образом, максимальное количество попыток совпадает с размером списка. Такое время выполнения называется линейным.

С бинарным поиском дело обстоит иначе. Если список состоит из 100 элементов, потребуется не более 7 попыток. Для списка из 4 миллиардов элементов потребуется не более 32 попыток. Таким образом, бинарный поиск выполняется за логарифмическое время.

Простой поиск	Бинарный поиск
100 элементов -> 100 попыток	100 элементов -> 7 попыток
4 000 000 000 элементов -> 4 000 000 000 попыток	4 000 000 000 элементов -> 32 попытки
O(n)	O(log n)

"О большое"

Специальная нотация "O большое" описывает скорость работы алгоритма. Зачем нам это? Время от времени нам придется использовать чужие алгоритмы, а потому было бы здорово понимать, насколько быстро или медленно они работают.

Время выполнения алгоритмов растет с разной скоростью

Программист Боб пишет алгоритм поиска для SpaceX. Его алгоритм заработает, когда ракета будет подлетать к Луне, и поможет вычислить точку посадки.

Это один из примеров того, как время выполнения двух алгоритмов растет с разной скоростью. Боб пытается выбрать между простым и бинарным поиском. Его алгоритм должен работать быстро и правильно. С одной стороны, бинарный поиск работает быстрее. У Боба есть всего 10 секунд, чтобы выбрать место посадки: если он не уложится в это время, то момент посадки будет упущен. С другой стороны, простой поиск пишется проще и вероятность ошибки в нем ниже. Конечно, Боб не хочет допустить ошибку в коде посадки ракеты. И тогда Боб решает измерить время выполнения обоих алгоритмов для списка из 100 элементов.

Допустим, проверка одного элемента занимает 1 миллисекунду. При простом поиске Бобу придется проверить 100 элементов, поэтому поиск займет 100 мс. С другой стороны, при бинарном поиске достаточно проверить всего 7 элементов (log_2 100 равен приблизительно 7), а поиск займет 7 мс. Но реальный список может содержать более миллиарда элементов. Сколько времени в таком случае потребуется для выполнения простого поиска? А при бинарном поиске?

Боб проводит бинарный поиск с 1 миллиардом элементов, и на это уходит 30 мс (log_2 1 000 000 000 равен приблизительно 30). Бинарный поиск работает с 15 раз быстрее простого, потому что простой поиск для 100 элементов занял 100 мс, а бинарный поиск занял 7 мс. Значит, простой поиск для миллиарда элементов займет 450 мс?

Нет, это ошибка. Время выполнения для простого поиска с 1 миллиардом элементов составит 1 миллиард мсек, а это 11 дней. Проблема в том, что время выполнения для бинарного и простого поиска растет с разной скоростью.

Количество элементов	Линейный поиск	Бинарный поиск
100 элементов	100 мс	7 мс
10 000 элементов	10 секунд	14 мс
1 000 000 элементов	11 дней	32 мс

Другими словами, с увеличением количества элементов бинарный поиск занимает чуть больше времени. В простой поиск займет гораздо больше времени. Таким образом, с увеличением списка бинарный поиск внезапно начинает работать гораздо быстрее простого. Боб думал, что бинарный поиск работает в 15 раз быстрее простого, но это не так. Если список состоит из 1 миллиарда элементов, бинарный поиск работает приблизительно в 33 миллиона раз быстрее. Вот почему недостаточно знать, сколько времени должен работать алгоритм - необходимо знать, как возрастает время выполнения с ростом размера списка. Здесь нам и пригодится "O большое".

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

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

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

"О большое" определяет время выполнения в худшем случае

Предположим, что вы используете линейный поиск для поиска фамилии в телефонной книге. Вы знаете, что простой поиск выполняется за время O(n), то есть в худшем случае вам придется просмотреть каждую без исключения запись в телефонной книге. Но представьте, что искомая фамилия начинается на букву "А" и этот человек стоит на самом первом месте в вашей телефонной книге. В общем, вам не пришлось просматривать все записи - вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм за время O(n)? А может, он занял время O(1), потому что результат был получен с первой попытки?

Простой поиск все равно выполняется за время O(n). Просто в данном случае вы нашли нужное значение моментально; это лучший возможный случай. Однако "О большое" описывает худший возможный случай. Фактически вы утверждаете, что в худшем случае придется просмотреть каждую запись в телефонной книге по одному разу. Это и есть время O(n). И это дает определенные гарантии - вы знаете, что простой поиск никогда не будет работать медленнее O(n).

Типичные примеры "О большого"

Ниже перечислены пять разновидностей "О большого", которые будут встречаться вам особенно часто, в порядке убывания скорости выполнения:

• O(log n) или логарифмическое время. Пример: бинарный поиск;

• O(n) или линейное время. Пример: простой поиск;

• O(n log n). Пример: эффективные алгоритмы сортировки;

• O(n^2). Пример: медленные алгоритмы сортировки;

• O(n!). Пример: алгоритм коммивояжера.

Существуют и другие варианты времени выполнения, но вышеперечисленные варианты встречаются чаще всего.

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

Подведем итоги:

• скорость работы алгоритмов измеряется не в секундах, а в темпе роста количества операций;

• по сути, формула "О большого" описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных;

• время выполнения алгоритмов выражается как "О большое";

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