Что такое алгоритм?
Алгоритм — это последовательность указаний, которые нужно исполнить, чтобы решить чётко сформулированную задачу. Мы описываем задачи исходя из ввода и вывода, и алгоритм становится способом превращения ввода в вывод. При этом формулировка задачи должна быть точной и недвусмысленной — это помогает избежать неверной интерпретации.
Когда вы закончили проектировать алгоритм, необходимо ответить на два важных вопроса: «Правильно ли он работает?» и «Сколько времени занимает выполнение?». Разумеется, вас не устроит алгоритм, который выдаёт правильный результат лишь в половине случаев или требует $1~000$ лет для поиска ответа.
Псевдокод
Чтобы понять, как работает алгоритм, нам необходимо перечислить шаги, которые он выполняет. Для этого мы будем использовать псевдокод — язык, которым пользуются разработчики для описания алгоритмов. Он игнорирует многие детали, необходимые в языках программирования, но он более точен, чем рецепт из кулинарной книги.
Задача и экземпляр задачи
Задача описывает класс возможных входных данных. Экземпляр задачи — это один конкретный ввод такого класса. Чтобы продемонстрировать понятия задачи и экземпляра задачи, рассмотрим следующий пример. Вы оказались в книжном магазине и собираетесь купить книгу за $4,23$$, расплатившись купюрой в $5$$. Вам должны вернуть $77$ центов в качестве сдачи. Теперь кассир принимает решение, как именно это сделать. Согласитесь, неприятно получить горсть из $77$ пенни или $15$ никелей и $2$ пенни. Возникает вопрос: как выдать сдачу, не расстроив клиента? Большинство кассиров стараются уместить сумму сдачи в наименьшее количество монет.
💡 Остановитесь и подумайте:
Каково минимальное количество монет номиналом $(25, 10, 5, 1)$, необходимо для сдачи в $77$ центов?
Пример с $77$ центами представляет собой экземпляр задачи Размен
. Предполагается, что есть $d$ номиналов, которые представлены массивом $c = (c_1, c_2, \dotsc, c_d)$. Для упрощения будем считать, что номиналы даны в порядке убывания. Например, $c = (25, 10, 5, 1)$ для монет, используемых в США.
Задача «Размен»
Переведите определенное количество денег в данные номиналы, используя как можно меньше монет.
- Входные данные: Целое число $money$ и массив из $d$ номиналов $c = (c_1, c_2, \dotsc, c_d)$ в порядке убывания ( $c_1 > c_2 > \dotsb > c_d$ ).
- Выходные данные: Список из $d$ целых чисел $i_1, i_2, \dotsc , i_d$, в котором $c_1\cdot i_1+c_2 \cdot i_2+\dotsm+ c_d \cdot i_d = money$ и $i_1 + i_2 +\dotsm +i_d$ как можно меньше.
Кассиры по всему миру решают эту проблему с помощью простого алгоритма:
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
Корректные и некорректные алгоритмы
Мы называем алгоритм корректным, если на каждый получаемый ввод он делает правильный вывод. Алгоритм считается некорректным, если хотя бы один ввод приводит к неправильному выводу.
💡 Остановитесь и подумайте:
Каково минимальное количество монет номиналами $(25, 20, 10, 5, 1)$, необходимое для сдачи в $40$ центов?
Change
— это некорректный алгоритм! Представьте сдачу в 40 центов, выданную в номиналах $c_1 = 25$, $c_2 = 20$, $c_3 = 10$, $c_4 = 5$ и $c_5 = 1$. Change
привел бы к неправильному результату: он выдал бы 1 четвертак (25 центов), 1 дайм (10 центов) и 1 никель (5 центов) вместо 2 монет по двадцать центов. Хоть это и может выглядеть надуманно, в 1875 году в США существовала монета в двадцать центов. Насколько мы можем быть уверены, что Change
выдаст минимальное количество монет в современных номиналах Соединенных Штатов или любой другой страны?
Чтобы исправить алгоритм Change
, нам нужно рассмотреть все возможные комбинации монет с номиналами $c_1, c_2, \dotsc , c_d$, которые дают в сумме $money$, и выдать комбинацию с минимальным количеством монет. Мы рассматриваем только комбинации, в которых $i_1 \le money/c_1$ и $i_2 \le money/c_2$ (в целом, величина $i_k$ не должна превышать $money/c_k$), в ином случае мы вернем большее количество денег, чем $money$. В псевдокоде, приведенном ниже, используется символ $\sum$. Он обозначает суммирование: $\sum^m_{i=1} a_i = a_1 + a_2 + \dotsm + a_m$. Псевдокод также использует концепт «бесконечность» (обозначается $\infty$) в качестве начального значения для $smallestNumberOfCoins$. Реализация описанного подхода на реальных языках программирования может различаться, но сейчас подробности для нас не важны.
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
Вторая строка повторяется с каждой возможной комбинацией $(i_1, \dotsc, i_d)$ из $d$ индексов и останавливается, когда достигает
$$ \left(\frac{money}{c_1}, \dotsc, \frac{money}{c_d}\right) $$
Как мы можем узнать, что BruteForceChange
не содержит ту же проблему, что и Change
, — неверный результат при каком-то вводе? Раз BruteForceChange
рассматривает все возможные комбинации номиналов, рано или поздно алгоритм придёт к оптимальному решению и запишет его в массив $change$. В любой комбинации монет, которая даёт в сумме $M$, должно быть как минимум столько же монет, сколько и в оптимальной. Таким образом, BruteForceChange
никогда не завершит работу с неоптимальным набором $change$.
На данный момент мы ответили только на один из двух важных вопросов об алгоритмах: "Работает ли он?". Однако мы не ответили на вопрос: "Сколько времени занимает выполнение?".
💡 Остановитесь и подумайте:
Сколько примерно итераций цикла for
выполняет BruteForceChange
?
- $money$
- $money^d$
- $d$
Быстрые и медленные алгоритмы
Настоящие компьютеры требуют определенное количество времени на выполнение таких операций, как сложение, вычитание или проверка условий цикла while. Суперкомпьютер может выполнить сложение за $10^{-10}$ секунды, а калькулятор — за $10^{-5}$. Представьте, что у вас есть компьютер, которому требуется $10^{-10}$ секунды на выполнение простой операции (например, сложения), и вы знаете, сколько операций выполняет какой-то конкретный алгоритм. Вы могли бы рассчитать время выполнения алгоритма, просто взяв произведение количества операций и времени, которое занимает одна операция. Однако компьютеры постоянно улучшаются, благодаря чему им требуется меньше времени на операцию. Так, ваше представление о времени выполнения быстро стало бы устаревшим. Вместо того, чтобы рассчитывать время выполнения на каждом компьютере, мы описываем время выполнения через общее количество операций, необходимых алгоритму, — это характеристика самого алгоритма, а не компьютера, который вы используете.
К сожалению, нам не всегда легко определить, сколько операций выполнит алгоритм. Однако если мы можем рассчитать количество базовых операций, выполняемых алгоритмом, то это позволит сравнить его с другим алгоритмом, решающим ту же задачу. Чтобы мучительно не подсчитывать каждое умножение и сложение, можно сравнивать только те участки кода, которые при увеличении размера ввода потребуют больше операций.
Представьте, что алгоритм $A$ выполняет $n^2$ операций при вводе размера $n$, и алгоритм $B$ решает ту же задачу за $3n+2$ операций. Какой алгоритм быстрее: $A$ или $B$? Хотя $A$ и может быть быстрее, чем $B$, при более малом значении $n$ (например, при $n$ между 1 и 3), $B$ будет быстрее при больших значениях $n$ (например, $n >4$). См. рис.. Так как $f(n)=n^2$ — это, в каком-то смысле, более «быстрорастущая» функция относительно $n$, чем $g(n)=n$. При этом константы 3 и 2 в $3n+2$ не влияют на конкуренцию между двумя алгоритмами при больших значениях $n$. Мы называем $A$ квадратичным алгоритмом и $B$ — линейным. $A$ менее эффективен, чем $B$, потому что он выполняет больше операций для решения задачи, когда значение $n$ большое. Так, иногда мы будем допускать неточности при подсчете операций алгоритма: поведение алгоритма при маленьком вводе неважно.
Рассчитаем примерное количество операций, которое потребуется для BruteForceChange
при вводе из $M$ центов и номиналов $(c_1, c_2, \dotsc, c_d)$. Чтобы рассчитать общее количество операций в цикле for, нам необходимо взять примерное число операций, выполняемое при каждой итерации, и умножить его на общее количество итераций. В нашем случае количество операций можно оценить сверху величиной
$$ \frac{money}{c_1} \times \frac{money}{c_2} \times \dotsm \times \frac{money}{c_d} $$
Такой тип алгоритмов называется экспоненциальным в противоположность квадратичным, кубическим или другим полиномиальным алгоритмам. Выражение времени выполнения экспоненциального алгоритма использует $n^d$, где $n$ и $d$ — это параметры задачи (например, $n$ и $d$ можно произвольно сделать большими, изменив ввод для алгоритма). Время выполнения полиномиального алгоритма ограничено $n^k$, где $k$ — это константа, не связанная с тестовыми данными.
Например, алгоритм с временем выполнения $n^1$ (линейный), $n^2$ (квадратичный), $n^3$ (кубический) или даже $n^{2018}$ будет полиномиальным. Конечно, алгоритм с временем выполнения $n^{2018}$ не очень практичен. Возможно, даже менее практичен, чем некоторые экспоненциальные алгоритмы. Впрочем, разработчики тратят много усилий, чтобы проектировать всё более и более быстрые полиномиальные алгоритмы. Раз значение $d$ может быть большим при вызове алгоритма с большим количеством номиналов (например, $c = (1, 2, 3, 4, 5, \dotsc , 100)$), мы видим, что выполнение BruteForceChange
может потребовать много времени.