Что такое алгоритм?
Алгоритм — это последовательность указаний, которые нужно исполнить, чтобы решить чётко сформулированную задачу. Мы описываем задачи исходя из ввода и вывода, и алгоритм становится способом превращения ввода в вывод. При этом формулировка задачи должна быть точной и недвусмысленной — это помогает избежать неверной интерпретации.
Когда вы закончили проектировать алгоритм, необходимо ответить на два важных вопроса: «Правильно ли он работает?» и «Сколько времени занимает выполнение?». Разумеется, вас не устроит алгоритм, который выдаёт правильный результат лишь в половине случаев или требует лет для поиска ответа.
Псевдокод
Чтобы понять, как работает алгоритм, нам необходимо перечислить шаги, которые он выполняет. Для этого мы будем использовать псевдокод — язык, которым пользуются разработчики для описания алгоритмов. Он игнорирует многие детали, необходимые в языках программирования, но он более точен, чем рецепт из кулинарной книги.
Задача и экземпляр задачи
Задача описывает класс возможных входных данных. Экземпляр задачи — это один конкретный ввод такого класса. Чтобы продемонстрировать понятия задачи и экземпляра задачи, рассмотрим следующий пример. Вы оказались в книжном магазине и собираетесь купить книгу за ＄, расплатившись купюрой в ＄. Вам должны вернуть центов в качестве сдачи. Теперь кассир принимает решение, как именно это сделать. Согласитесь, неприятно получить горсть из пенни или никелей и пенни. Возникает вопрос: как выдать сдачу, не расстроив клиента? Большинство кассиров стараются уместить сумму сдачи в наименьшее количество монет.
💡 Остановитесь и подумайте:
Каково минимальное количество монет номиналом , необходимо для сдачи в центов?
Пример с центами представляет собой экземпляр задачи Размен. Предполагается, что есть номиналов, которые представлены массивом . Для упрощения будем считать, что номиналы даны в порядке убывания. Например, для монет, используемых в США.
Задача «Размен»
Переведите определенное количество денег в данные номиналы, используя как можно меньше монет.
- Входные данные: Целое число и массив из номиналов
в порядке убывания ( ). - Выходные данные: Список из целых чисел , в котором и как можно меньше.
Кассиры по всему миру решают эту проблему с помощью простого алгоритма:
Change(money, c, d):
while money > 0:
coin = ... // монета с самым большим номиналом, который не превышает money
// дать монету с номиналом coin клиенту
money = money - coin
Вот быстрая версия Change:
Change(money, c, d):
for k in range(1, d + 1)
i_k = floor(money / c[k]) // наибольшее количество монет номинала c[k]
// дать i_k монет с номиналом c[k] клиенту
money = money - c[k] * i_k
Корректные и некорректные алгоритмы
Мы называем алгоритм корректным, если на каждый получаемый ввод он делает правильный вывод. Алгоритм считается некорректным, если хотя бы один ввод приводит к неправильному выводу.
💡 Остановитесь и подумайте:
Каково минимальное количество монет номиналами , необходимое для сдачи в центов?
Change — это некорректный алгоритм! Представьте сдачу в 40 центов, выданную в номиналах , , , и . Change привел бы к неправильному результату: он выдал бы 1 четвертак (25 центов), 1 дайм (10 центов) и 1 никель (5 центов) вместо 2 монет по двадцать центов. Хоть это и может выглядеть надуманно, в 1875 году в США существовала монета в двадцать центов. Насколько мы можем быть уверены, что Change выдаст минимальное количество монет в современных номиналах Соединенных Штатов или любой другой страны?
Чтобы исправить алгоритм Change, нам нужно рассмотреть все возможные комбинации монет с номиналами , которые дают в сумме , и выдать комбинацию с минимальным количеством монет. Мы рассматриваем только комбинации, в которых и (в целом, величина не должна превышать ), в ином случае мы вернем большее количество денег, чем . В псевдокоде, приведенном ниже, используется символ . Он обозначает суммирование: . Псевдокод также использует концепт «бесконечность» (обозначается ) в качестве начального значения для . Реализация описанного подхода на реальных языках программирования может различаться, но сейчас подробности для нас не важны.
BruteForceChange(money, c, d):
smallestNumberOfCoins = ∞
for each combinations of coins (i_1,...,i_d)
// от (0,...,0) до (money/c[1],...,money/c[d])
valueOfCoins = ∑ i_k*c_k // сумма по всем k от 1 до d
if valueOfCoins = money:
numberOfCoins = ∑ i_k // суммарное количество монет
if numberOfCoins < smallestNumberOfCoins:
smallestNumberOfCoins = numberOfCoins
change = (i_1, i_2, ... ,i_d)
return change
Цикл повторяется с каждой возможной комбинацией из индексов и останавливается, когда достигает
Как мы можем узнать, что BruteForceChange не содержит ту же проблему, что и Change, — неверный результат при каком-то вводе? Раз BruteForceChange рассматривает все возможные комбинации номиналов, рано или поздно алгоритм придёт к оптимальному решению и запишет его в массив . В любой комбинации монет, которая даёт в сумме , должно быть как минимум столько же монет, сколько и в оптимальной. Таким образом, BruteForceChange никогда не завершит работу с неоптимальным набором .
На данный момент мы ответили только на один из двух важных вопросов об алгоритмах: "Работает ли он?". Однако мы не ответили на вопрос: "Сколько времени занимает выполнение?".
💡 Остановитесь и подумайте:
Сколько примерно итераций цикла for выполняет BruteForceChange?
Быстрые и медленные алгоритмы
Настоящие компьютеры требуют определенное количество времени на выполнение таких операций, как сложение, вычитание или проверка условий цикла while. Суперкомпьютер может выполнить сложение за секунды, а калькулятор — за . Представьте, что у вас есть компьютер, которому требуется секунды на выполнение простой операции (например, сложения), и вы знаете, сколько операций выполняет какой-то конкретный алгоритм. Вы могли бы рассчитать время выполнения алгоритма, просто взяв произведение количества операций и времени, которое занимает одна операция. Однако компьютеры постоянно улучшаются, благодаря чему им требуется меньше времени на операцию. Так, ваше представление о времени выполнения быстро стало бы устаревшим. Вместо того, чтобы рассчитывать время выполнения на каждом компьютере, мы описываем время выполнения через общее количество операций, необходимых алгоритму, — это характеристика самого алгоритма, а не компьютера, который вы используете.
К сожалению, нам не всегда легко определить, сколько операций выполнит алгоритм. Однако если мы можем рассчитать количество базовых операций, выполняемых алгоритмом, то это позволит сравнить его с другим алгоритмом, решающим ту же задачу. Чтобы мучительно не подсчитывать каждое умножение и сложение, можно сравнивать только те участки кода, которые при увеличении размера ввода потребуют больше операций.
Представьте, что алгоритм выполняет операций при вводе размера , и алгоритм решает ту же задачу за операций. Какой алгоритм быстрее: или ? Хотя и может быть быстрее, чем , при более малом значении (например, при между 1 и 3), будет быстрее при больших значениях (например, ). См. рис.. Так как — это, в каком-то смысле, более «быстрорастущая» функция относительно , чем . При этом константы 3 и 2 в не влияют на конкуренцию между двумя алгоритмами при больших значениях . Мы называем квадратичным алгоритмом и — линейным. менее эффективен, чем , потому что он выполняет больше операций для решения задачи, когда значение большое. Так, иногда мы будем допускать неточности при подсчете операций алгоритма: поведение алгоритма при маленьком вводе неважно.
Рассчитаем примерное количество операций, которое потребуется для BruteForceChange при вводе из центов и номиналов . Чтобы рассчитать общее количество операций в цикле for, нам необходимо взять примерное число операций, выполняемое при каждой итерации, и умножить его на общее количество итераций. В нашем случае количество операций можно оценить сверху величиной
Такой тип алгоритмов называется экспоненциальным в противоположность квадратичным, кубическим или другим полиномиальным алгоритмам. Выражение времени выполнения экспоненциального алгоритма использует , где и — это параметры задачи (например, и можно произвольно сделать большими, изменив ввод для алгоритма). Время выполнения полиномиального алгоритма ограничено , где — это константа, не связанная с тестовыми данными.
Например, алгоритм с временем выполнения (линейный), (квадратичный), (кубический) или даже будет полиномиальным. Конечно, алгоритм с временем выполнения не очень практичен. Возможно, даже менее практичен, чем некоторые экспоненциальные алгоритмы. Впрочем, разработчики тратят много усилий, чтобы проектировать всё более и более быстрые полиномиальные алгоритмы. Раз значение может быть большим при вызове алгоритма с большим количеством номиналов (например, ), мы видим, что выполнение BruteForceChange может потребовать много времени.