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

Проблема секунд

Измеренное время зависит от процессора, версии Python, нагрузки и кеша. Один и тот же код на ноутбуке может занять 2 секунды, на сервере 0,5 секунды. А алгоритм один и тот же. Нужно число элементарных операций как функция размера входа n.

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

Модель

  • Размер входа n: длина списка, число символов строки, число вершин и рёбер графа.
  • Элементарная операция: присваивание, сравнение, арифметика, обращение по индексу; каждая — один шаг.
  • f(n): число шагов алгоритма. Нас интересует её характер роста.

При вложенных циклах шаги перемножаются:

python
def count_linear(n):
    ops = 0
    for _ in range(n):
        ops += 1
    return ops