Знаешь что такое временная сложность алгоритма?

В детстве учили умножать числа, говорили, что смысл умножения в том, чтобы коротко записать сумму. Например, 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. И ещё за это же время работают некоторые не очень эффективные по времени алгоритмы сортировки, например, сортировка пузырьком

Источник: Python Deph