Автор: CoolPython
Когда в детстве меня учили умножать числа, мне говорили, что смысл умножения в том, чтобы короче записать сумму. Например, 4 * 3 это то же, что 4 + 4 + 4.
Сведение умножения к сумме — самый простой, наивный алгоритм умножения. А теперь я возьму мой рабочий ноут и попробую перемножить этим способом какие-нибудь большие числа, например, 4 * 10000000000:
sum = 0
for i in range(0, 10000000000):
sum += 4
print(sum)
Если я попробую посчитать то же самое на калькуляторе, то замечу, что лаптоп отрабатывает заметно медленнее, несмотря на то, что он мощнее. Почему? Потому что для умножения чисел существует несколько алгоритмов, а я выбрала самый неэффективный из них. Ещё есть, например, метод Карацубы, или алгоритм на основе преобразования Фурье. В калькуляторах обычно используется второй, и он требует значительно меньше операций, чем наивный.
Как понять, быстро ли работает алгоритм? Можно попробовать измерить время напрямую:
import time start = time.time() my_awesome_alg() end = time.time() print(end - start)
Но мы обнаружим, что скорость зависит от производительности машины, от ее архитектуры и загруженности в момент выполнения программы. Поэтому физическое время никак не поможет нам оценить эффективность алгоритма.
Чтобы уйти от физических свойств вычислителя, используют понятие сложности. Асимптотическая сложность алгоритма — это то, как изменяется время исполнения в зависимости от объема входных данных. В этом определении намеренно не учитывается то, на каком устройте выполняется алгоритм: это может быть компьютер, калькулятор или даже человек. Такой абстрактный вычислитель называют машиной Тьюринга.
При этом разделяют сложность алгоритма в худшем и лучшем случае. Представьте, что мы хотим проверить, есть ли в списке число 42. Мы проверяем первый элемент на равенство 42, второй, третий… В лучшем случае первый элемент окажется искомым. В худшем — последний. Поэтому обычно рассматривают сложность алгоритма в наилучшем, наихудшем случае, и в среднем. Как правило, пессимистическая оценка самая интересная из всех, потому что позволяет планировать объем ресурсов.
Временную сложность алгоритма в худшем случае выражают с использованием нотации «O» большое. В этом случае из рассмотрения исключают члены меньшего порядка и говорят об изменении используемых ресурсов при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения работы, для всех входов длины n не превосходит 5n^3 + 3n, то асимптотическая временная сложность равна O(n^3).
Рассмотрим несколько примеров
O(1)
Время, которое не зависит от объема входных данных, или постоянное время. За постоянное время можно получить элемент массива по индексу или добавить элемент в связный список.
O(n)
Алгоритм, в котором мы идём по списку, чтобы узнать, есть ли в нем значение 42, в худшем случае требует O(n) операций, где n — длина списка. Такую же сложность имеет сравнение строк, потому что по сути оно тоже требуют обхода всей строки.
O(log n)
Проверить, есть ли значение 42 в списке, можно быстрее, чем за O(n), если список отсортирован. Тогда можно проверить на равенство элемент из середины списка. Если он равен 42, то останавливаемся. Если больше — значит, слева можно не искать, там значения только меньше. Будем продолжать проверку, выбирая каждый раз элемент из середины оставшегося отрезка. Этот алгоритм называют бинарным поиском и он имеет логарифмическую сложность, потому что количество вариантов уменьшается каждый раз на 2, как функция, обратная степенной (она же логарифм).
O(n log n)
Можно показать, что большинство алгоритмов сортировки имеют сложность n log(n). За время n log(n) работают сортировка слиянием, кучей, и быстрая сортировка. Еще есть теорема, которая говорит, что если сортировка основана на сравнении элементов, то быстрее, чем за n log(n) отсортировать элементы не получится.
O(n^2)
За время n^2 работает обход двумерного массива, это можно представить себе как обход таблицы n * n. И ещё за это же время работают некоторые не очень эффективные по времени алгоритмы сортировки, например, сортировка пузырьком.
Для разработчика важно иметь интуицию насчет временной сложности алгоритмов, потому что за счет неэффективности вычислений можно загубить производительность самого мощного железа, как это случилось, когда калькулятор побил мой мощный ноутбук. Поэтому этой науке уделяется большое внимание в разработке. 95%, что на собеседовании вам предложат алгоритмическую задачу и попросят оценить время выполнения вашего решения.
Если вы хотите углубиться в теорию алгоритмов, то я советую специализацию Алгоритмы и структуры данных на Курсере. Теория здесь изложена доступно и в курсе есть задачи, чтобы набить руку. А еще есть Стенфордский учебник по теории сложности, он написан замечательным языком и в нем прекрасные примеры.
