Часть 1.
Когда в детстве меня учили умножать числа, мне говорили, что смысл умножения в том, чтобы короче записать сумму. Например, 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). 🤓