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