Одну и ту же задачу можно решить десятком разных способов. Как понять, какой из них лучше?
Можно измерить чистое время выполнения в секундах, но это ненадежно — зависит от аппаратной конфигурации и объема исходных данных. Поэтому придумали мерить сложность алгоритма в терминах количества операций.
Считать точное количество операций слишком хлопотно. Поэтому его описывают как зависимость от числа
N — количества исходных данных, на которых работает алгоритм.Такую оценку называют «Big-O» или «асимптотическим анализом» (потому что она работает для больших значений N).
Вот распространенные оценки алгоритмов от более быстрых (мало операций) к более медленным (много операций):
Константная сложность O(1)
Время выполнения алгоритма не зависит от объема исходных данных. Идеальный алгоритм!
Например, выбрать элемент из списка по индексу:
lst = [random.random() for _ in range(n)]
idx = random.randint(0, n-1)
# O(1)
lst[idx]
Логарифмическая O(log n)
При увеличении
n время выполнения алгоритма растет такими же темпами, как log(n). Логарифм растет медленно (log 1000000 ≈ 20), так что даже при больших n логарифмические алгоритмы работают достаточно быстро.Например, найти элемент в отсортированном списке:
el = random.random()
sorted_lst = sorted(lst)
# O(log n)
bisect.bisect(sorted_lst, el)
Линейная O(n)
Время выполнения алгоритма растет такими же темпами, как
n. Как правило, такие алгоритмы перебирают все исходные данные.Например, найти элемент в неотсортированном списке:
el = random.random()
# O(n)
idx = lst.index(el)
Линейно-логарифмическая O(n log n)
Время выполнения алгоритма растет такими же темпами, как
n × log(n). Алгоритм получается медленнее, чем O(n), но не слишком (логарифм n намного меньше n, помните?).Например, отсортировать список:
# O(n log n)
sorted(lst)
Продолжение следует ツ Если что непонятно — спрашивайте в комментариях.
#код