1.4. Алгоритмы и сложность

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

Также вы познакомитесь с понятием временной сложности и увидите разницу между «медленными» и «быстрыми» алгоритмами.

Ключевые вопросы параграфа

• Чем задача отличается от её конкретного экземпляра и зачем это различие важно?
• Какие ошибки может допустить алгоритм и как проверить его корректность?
• В чём преимущества описания алгоритма на псевдокоде?
• Как измерять «быстроту» алгоритма и почему не всегда важно абсолютное время работы?
• Почему полиномиальные алгоритмы считаются приемлемыми, а экспоненциальные — проблемными?

Что такое алгоритм?

Алгоритм — это последовательность указаний, которые нужно исполнить, чтобы решить чётко сформулированную задачу. Мы описываем задачи, исходя из ввода и вывода, и алгоритм становится способом превращения ввода в вывод. При этом формулировка задачи должна быть точной и недвусмысленной — это помогает избежать неверной интерпретации.

Когда вы закончили проектировать алгоритм, необходимо ответить на два важных вопроса: «Правильно ли он работает?» и «Сколько времени занимает выполнение?».

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

Псевдокод

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

Задача и экземпляр задачи

Задача описывает класс возможных входных данных.

Экземпляр задачи — это один конкретный ввод такого класса. Чтобы продемонстрировать понятия задачи и экземпляра задачи, рассмотрим следующий пример.

Пример

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

Пример с центами представляет собой экземпляр задачи Размен. Предполагается, что есть номиналов, которые представлены массивом . Для упрощения будем считать, что номиналы даны в порядке убывания. Например, для монет, используемых в США.

Задача «Размен»

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

• Входные данные: Целое число и массив из номиналов
  в порядке убывания ( ).
• Выходные данные: Список из целых чисел , в котором и как можно меньше.

Кассиры по всему миру решают эту проблему с помощью простого алгоритма:

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 никогда не завершит работу с неоптимальным набором .

На данный момент мы ответили только на один из двух важных вопросов об алгоритмах: "Работает ли он?". Однако мы не ответили на вопрос: "Сколько времени занимает выполнение?".

Быстрые и медленные алгоритмы

Настоящие компьютеры требуют определенное количество времени на выполнение таких операций, как сложение, вычитание или проверка условий цикла while. Суперкомпьютер может выполнить сложение за секунды, а калькулятор — за .

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

Однако компьютеры постоянно улучшаются, благодаря чему им требуется меньше времени на операцию. Так, ваше представление о времени выполнения быстро стало бы устаревшим.

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

Как определить количество операций алгоритма

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

Представьте, что алгоритм выполняет операций при вводе размера , и алгоритм решает ту же задачу за операций. Какой алгоритм быстрее: или ? Хотя и может быть быстрее, чем , при более малом значении (например, при между 1 и 3), будет быстрее при больших значениях (например, ). (См. рис.). Так как — это, в каком-то смысле, более «быстрорастущая» функция относительно , чем .

При этом константы 3 и 2 в не влияют на конкуренцию между двумя алгоритмами при больших значениях . Мы называем квадратичным алгоритмом и — линейным. менее эффективен, чем , потому что он выполняет больше операций для решения задачи, когда значение большое. Так, иногда мы будем допускать неточности при подсчете операций алгоритма: поведение алгоритма при маленьком вводе неважно.

Пример расчёта количества операций для BruteForceChange

Рассчитаем примерное количество операций, которое потребуется для BruteForceChange при вводе из центов и номиналов . Чтобы рассчитать общее количество операций в цикле for, нам необходимо взять примерное число операций, выполняемое при каждой итерации, и умножить его на общее количество итераций. В нашем случае количество операций можно оценить сверху величиной

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

Выражение времени выполнения экспоненциального алгоритма использует , где и — это параметры задачи (например, и можно произвольно сделать большими, изменив ввод для алгоритма).

Время выполнения полиномиального алгоритма ограничено , где — это константа, не связанная с тестовыми данными.

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

Впрочем, разработчики тратят много усилий, чтобы проектировать всё более и более быстрые полиномиальные алгоритмы. Раз значение может быть большим при вызове алгоритма с большим количеством номиналов (например, ), мы видим, что выполнение BruteForceChange может потребовать много времени.

Что дальше

Теперь вы знаете, что такое алгоритм, чем задача отличается от её экземпляра и как алгоритмы помогают решать поставленные задачи. Вы познакомились с псевдокодом, понятием корректности алгоритма и идеей оценки его эффективности. А ещё узнали, почему время выполнения важно и как отличать «быстрые» алгоритмы от «медленных» с точки зрения роста числа операций.

А пока вы не ушли дальше — закрепите материал на практике:

• Отметьте, что урок прочитан, при помощи кнопки ниже.

• Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• Алгоритм — это способ преобразования входных данных в выходные. Он решает задачу, формулируемую через множество возможных входов и условий.

• Псевдокод помогает описывать шаги алгоритма понятно и точно, а корректность означает, что алгоритм всегда выдаёт правильный результат.

• Эффективность алгоритма оценивается по количеству операций, которые он выполняет, — это позволяет сравнивать алгоритмы независимо от устройства.

• Полиномиальные алгоритмы масштабируются лучше и считаются эффективными, тогда как экспоненциальные быстро становятся непрактичными при росте входных данных.

В следующей главе вы познакомитесь со структурами данных: стеком, очередью, словарём, множеством и списками. Вы узнаете, как они устроены, где используются и чем отличаются друг от друга, — а заодно научитесь применять их в задачах.