Знакомство с алгоритмами

Знакомство с алгоритмами

Введение

Алгоритмом называется набор инструкций для выполнения некоторой задачи. В принципе любой работающий фрагмент программного кода можно назвать алгоритмом. В данной статье рассмотрим алгоритм двоичного или бинарного поиска. Данный алгоритм например позволяет сократить количество необходимых операций поиска с 1 миллиарда до 30! Вот ещё некоторые примеры применения алгоритмов. Устройства GPS используют алгоритмы из теории графов. При помощи методов динамического программирования можно создать алгоритм для игры в шашки.

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

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

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

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

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

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

Допустим, вы ищите фамилию человека в телефонном справочнике(книге). Она начинается на букву "М" и можно конечно начать искать с самого начала и идти по каждой странице, пока не доберётесь до буквы "М". Но для ускорения поиска лучше раскрыть справочник на середине(буква "М" как раз должна находится где-то ближе к середине книги). Теперь допустим что вы вводите свои данные на каком нибудь сайте(в ВК например). При этом сайту необходимо будет проверить, есть ли у вас учётная запись. Например, вы выбрали себе ник(имя пользователя) "karlmarks". Сайт может начать с буквы "a" и проверять все логины подряд, но разумнее будет опять же начать с середины. Перед нами задача поиска. И во всех этих случаях можно применить один алгоритм: бинарный(двоичный) поиск.

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

Рассмотрим пример. Вы должны отгадать моё число от 1 до 100. При каждой попытке я буду давать один из трёх ответов: "много", "мало" или "угадано". Допустим, вы начинаете перебирать все варианты подряд: 1,2,3,4,5,... Это пример простого поиска(или даже "тупого"). При каждой догадке исключается только одно число. Если я загадал число 48, то, чтобы добраться до него, потребуется 48 попыток(или 52 если идти с конца 100, 99, 98, ...)! Тут то и может прийти на помощь бинарный поиск. Сразу начнём с середины — с 50. - "Много". Но вы исключили сразу половину чисел. Теперь вы знаете что числа больше 50(50-100) будут больше загаданного. Следующая попытка алгоритма: 25. - "Мало". На этот раз "недолёт". Но вы снова исключили половину оставшихся чисел! Получается что, с бинарным поиском каждый отбрасывается половина диапазона! Следующим будет число: 38(посередине между 25 и 50) и т.д. Пока не будет найдено загаданное число. Попробуем определить точнее, сколько чисел будет исключаться каждый раз?

И так получается что, какое бы число я не загадал от 1 до 100, с помощью алгоритма бинарного поиска, вы отгадаете его точно за 7 попыток.

Выполните простое упражнение: вы ищите слово в словаре с 200000 словами. Как вы думаете, сколько попыток вам понадобится в худшем случае? При простом поиске может потребоваться до 200000 попыток, если вы начала сначала, а искомое слово находится на самом последнем месте. Но если вы использовали бинарный поиск, то количество слов сокращается вдвое, пока не останется только одно искомое слово.

Итак, бинарный поиск отнимет всего 18 шагов!

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

Логарифм — обратная операция возведению в степень. это означает, сколько раз нужно перемножить число 10, чтобы получить число 100.
Когда я буду писать я буду иметь в виду это означает, сколько раз нужно перемножить число 2, чтобы получить 100.

Итак, мы получили закономерность. Для списка из 8 чисел максимально может потребоваться 8 проверок. Для того же списка с применением алгоритма бинарного поиска потребуется: потому что Для списка из 512 элементов с применением алгоритма бинарного поиска потребуется: потому что Следовательно, для списка из 512 чисел придётся проверить не более 9 чисел.

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

Рассмотрим, как запрограммировать реализацию бинарного поиска на Python. В следующем примере кода используется список.

Поскольку в Python массивы называются списками, термины массив и список часто используются как взаимозаменяемые. Но в реализациях алгоритмов на различных языках программирования могут быть отличия при создании списков(с возможностью увеличения количества элементов) либо массивов(с заранее ограниченным числом элементов).

Чтобы понять работу самого алгоритма, нам достаточно пока будет знать, что серию элементов можно сохранить в непрерывной последовательности ячеек, которая называется массивом. Нумерация ячеек в которых хранятся сами элементы массива начинается с 0: первая ячейка имеет позицию с индексом(номером) 0, вторая — в позиции 1 и так далее. Для реализации любых алгоритмов лучше всего написать функцию. Что такое функции? Также минимум нужно знать, что они принимают значения(например массив) и внутри себя что-то с ними делают и наконец возвращают результат. Функцию так и назовём binary_search, которая будет получать на вход отсортированный массив(список) и значение. Если значение присутствует в массиве, то функция возвращает его позицию(номер или индекс). При этом мы должны следить внутри функции за тем, в какой части массива проводится поиск. В самом начале это весь массив:

low = 0
high = len(list) - 1

Каждый раз алгоритм проверят средний элемент:

mid = (low + high) // 2
guess = list[mid]

Если названое число было слишком велико, то переменная high обновляется:

if guess > item:
    high = mid - 1

А если догадка была слишком мала, то обновляется переменная low.

Полный код выглядит так:

def search_iterative(self, list, item):
# в переменных low и high хранятся границы той части списка, в которой выполняется поиск
low = 0
high = len(list) - 1
# Пока эта часть не сократится до одного элемента ...
while low <= high:
  # ... проверяем средний элемент
  mid = (low + high) // 2
  guess = list[mid]
  # Если значение найдено возвращаем его номер(индекс списка)
  if guess == item:
    return mid
  # Если найдено значение больше - уменьшаем верхний индекс(границу)
  if guess > item:
    high = mid - 1
  # Если найдено значение меньше - увеличиваем нижний индекс(границу)
  else:
    low = mid + 1
# Элемент не найден
return None

После того как создали функцию, можно её протестировать:

my_list = [1, 3, 5, 7, 9]  # Список с отсортированными элементами(обязательно по возрастанию)
print(search_iterative(my_list, 3)) # => 1 — нумерация с 0.
# "None" в Python означает ничего. Мы используем для обозначения того, что элемент не найден.
print(search_iterative(my_list, -1)) # => None

Попробуйте сами скопировать и запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.

Полную реализацию алгоритма вы можете скачать ниже по ссылке(скачать файл):

Если скачали и увидели реализацию алгоритма с помощью "рекурсии" и создание класса? Чтобы понять эту реализацию бинарного поиска, нужно разобраться отдельно что же такое рекурсивные алгоритмы и создание классов в Python.

Двоичный поиск является одной из реализаций техники построения алгоритмов под названием разделяй и властвуй (divide and conquer, D&C). Алгоритмы D&C решают одну или более независимых подзадач, после чего совмещают их решения для поиска решения исходной задачи (двоичный поиск решает только одну подзадачу, соответствующую той части входных данных, о которой известно, что она содержит решение, в то время как другие алгоритм D&C обычно решают две или более подзадач). Чтобы больше узнать об этом семействе алгоритмов и некоторых задачах, которые они эффективно решают, советую книгу Тима Рафгардена(Tim Roughgarden) Совершенный алгоритм. Основы. СПб.: Питер.

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

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

Обсудим время выполнения бинарного поиска. Если список состоит из 100 элементов, то при линейном поиске может потребоваться до 100 попыток. Для списка из 4 миллиардов элементов(чисел) потребуется до 4 миллиардов попыток. Таким образом, максимальное количество попыток соответствует размеру массива(списка). Такое время выполнение называется линейным и обозначается как O(n). С бинарным поиском дело обстоит иначе. Если список состоит из 100 элементов, потребуется не более 7 попыток. Для списка из 4 миллиардов элементов потребуется не более 32 попыток. Соответственно бинарный поиск выполняется за логарифмическое время и обозначается как O(lbn) (имеется ввиду двоичный логарифм — логарифм по основанию 2).

"О-большое"

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

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

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

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

Иван проводит бинарный поиск с 1 миллиардом элементов, и на это уходит 30 мс(lb2 1000000000 равен примерно 30). Иван думает, что бинарный поиск в 15 раз быстрее простого, потому что линейный поиск для 100 элементов занял 100 мс, а бинарный всего 7 мс. Значит, линейный поиск с 1 миллиардом элементов займёт 30 * 15 = 450 мс, так? Гораздо меньше отведённых 10 секунд? И Иван выбирает линейный поиск. Верен ли его выбор?

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

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

Простыми словами, с увеличением количества элементов бинарный поиск займёт чуть больше времени, тогда как линейный займёт гораздо больше времени! Если список состоит из 1 миллиарда элементов, то бинарный поиск работает приблизительно в 33 миллиона раз быстрее линейного! Вот почему недостаточно знать, сколько времени отработает алгоритм — необходимо знать, как возрастает время выполнения с ростом размера количества выполняемых им операций. "О-большое" как раз описывает, насколько быстро работает алгоритм. Предположим, имеется список размера n. Время выполнения "О-большое" простого линейного поиска в общем случае выглядит как:

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

Теперь рассмотрим несколько примеров и попробуем оценить время выполнения алгоритмов.

Наглядное представление "О-большое"

Допустим вы должны построить сетку из 16 квадратов. Для этого достаточно иметь несколько листков бумаги и карандаш.

Как должен выглядеть алгоритм построения такой сетки?

Алгоритм 1

Нарисовать 16 квадратов, по одному за раз. В данном примере рисование квадрата считается одной операцией. Нужно нарисовать 16 квадратов. Сколько операций по рисованию квадрата придётся выполнить? Чтобы нарисовать 16 квадратов, потребуется 16 шагов. Как выглядит время выполнения алгоритма?

Ответ: O(n).

Алгоритм 2

А теперь попробуем так. Сложите лист пополам. На этот раз операцией считается сложение листка. Получается, что одна операция создаёт сразу два прямоугольника. Сложите затем ещё раз, а потом ещё и ещё. И наконец, разверните листок после четырёх сложений — получилась сетка! Каждое сложение удваивает количество прямоугольников. Получилось, что за 4 операции создаётся 16 прямоугольников! При каждом складывании количество прямоугольников увеличивается вдвое! Как записать время выполнения этого алгоритма?

Ответ:

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

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

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

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

Примеры "О-большого"

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

• O(lbn), или логарифмическое время. Пример: бинарный поиск.
• O(n), или линейное время. Пример: простой поиск.
• О(n * lbn). Пример: эффективные алгоритмы сортировки(быстрая сортировка).
• О(n * n). Пример: медленные алгоритмы сортировки(сортировка выбором).
• O(n!). Пример: очень медленные алгоритмы(задача о коммивояжере).

Допустим, вы снова строите сетку из 16 квадратов и можете выбрать для решения задачи один из пяти алгоритмов. При использовании первого алгоритма сетка будет построена за время O(lbn). В секунду выполняются до 10 операций. С временем O(lbn) для построения сетки из 16 квадратов потребуются 4 операции(lbn16 = 4). Итак, сетка будет построена за 0,4 секунды. А если бы было нужно построить 1024 квадрата? То O(lbn) = lb1024 = 10 операций или ровно 1 секунда. Эти числа получены при использовании первого алгоритма.

Второй алгоритм работает медленнее: за время O(n). Для построения 16 прямоугольников нужно 16 операций, а для построения 1024 прямоугольников — 1024 операции. Сколько времени это займёт?

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

Эти записи являются упрощением. На практике не всегда удаётся легко преобразовать время выполнения в количество операций в секунду с такой точностью. Основные выводы:

• Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций;
• Формула в аннотации "О-большое" описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных;
• Время выполнения алгоритмов выражается как "О-большое";
• Время выполнения O(lbn) быстрее O(n). С увеличением размера массива(списка), в котором происходит поиск значения, оно кратно быстрее.

Задача о коммивояжере

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

Смысл задачи в следующем: коммивояжер должен объехать города, например пусть будет пять городов. Коммивояжер хочет побывать в каждом из 5 городов так, чтобы при это ещё проехать минимальное общее расстояние. Одно из возможных решений: перебрать все возможные комбинации порядка объезда городов. Все расстояния суммируются, после чего выбирается путь с кратчайшим расстоянием. Для 5 городов можно создать 120 перестановок, поэтому решение задачи для 5 городов потребует 120 операций. Для 6 городов количество операций увеличивается до 720(существует уже 720 возможных перестановок). А для 7 городов потребуется уже 5040 операций! Количество операций стремительно растёт!

В общем случае для вычисления результата при n элементах потребуется n-факториал операций. Значит время выполнения составит O(n!) и такое время называется факториальным. Можно сделать вывод: если вы попытаетесь решить задачу для 100+ городов, то сделать этот вовремя не удастся. И как бы ни было это печально, но у задачи коммивояжера нет другого решения! Это одна из самых знаменитых задач в теории вычислений! Считается что для этой задачи можно найти лишь приближенное решение(с помощью жадного алгоритма).

P.S. Подробнее об остальных алгоритмов будет в следующих статьях.