Как смотреть сложность кода

Прежде чем разбирать классы — общее правило. Сложность определяется тем, сколько операций функция выполняет в зависимости от размера входа n. Ключевые признаки:

• Один проход по входу -> вклад n.
• Вложенный проход -> вклад n².
• Деление пополам на каждом шаге -> вклад log n.
• Удвоение работы при +1 к n -> вклад 2^n.

Итоговая сложность — сумма вкладов с доминирующим членом. Если у функции один цикл O(n) и потом сортировка O(n log n), то итог O(n log n).

Теперь по классам.

O(1) — константная сложность

Время не зависит от размера. Самый дешёвый класс. Примеры:

def first(lst):
    return lst[0]  # O(1) — array access по индексу

def add_to_set(s, x):
    s.add(x)       # O(1) среднее — hash + insert

def get_value(d, key):
    return d[key]  # O(1) среднее — dict lookup

Тут важная оговорка: O(1) часто означает «среднее», не «худший случай». У dict в худшем случае O(n) (все ключи в одну корзину коллидируют), но на практике это не происходит. Об этом — в модуле про хеш-таблицы.

Замер:

import timeit

setup = "lst = list(range(n))"
for n in [10, 1000, 100_000, 10_000_000]:
    t = min(timeit.repeat(
        'lst[0]',
        setup=setup.replace('n', str(n)),
        number=1_000_000,
        repeat=5
    )) / 1_000_000
    print(f"n={n:>10}: {t*1e9:.1f} ns per access")

Типичный вывод:

n=        10: 11.4 ns per access
n=      1000: 11.5 ns per access
n=    100000: 11.5 ns per access
n=  10000000: 11.6 ns per access

Видим: при росте n в миллион раз время практически не меняется. Это и есть O(1). Колебания на пару процентов — шум измерения.

O(log n) — логарифмическая сложность

Появляется там, где работа на каждом шаге делится пополам. Классический пример — бинарный поиск:

def binary_search(sorted_lst, target):
    lo, hi = 0, len(sorted_lst) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_lst[mid] == target:
            return mid
        elif sorted_lst[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

На каждом шаге пространство поиска делится пополам. Если n=1M, то после 20 шагов от него ничего не остаётся (2²⁰ = 1048576). Поэтому сложность — O(log n).

В Python для бинарного поиска используют модуль bisect:

import bisect
import timeit

setup = """
import bisect
lst = list(range(n))
"""

for n in [1_000, 100_000, 10_000_000]:
    t = min(timeit.repeat(
        'bisect.bisect_left(lst, n // 2)',
        setup=setup.replace('n // 2', str(n // 2)).replace('n', str(n)),
        number=100_000,
        repeat=5
    )) / 100_000
    print(f"n={n:>10}: {t*1e9:.0f} ns")

Типичный вывод:

n=      1000:  280 ns
n=    100000:  430 ns
n=  10000000:  640 ns

Заметьте: рост n в 10000 раз дал рост времени всего в 2.3 раза. log₂(10000) ≈ 13.3, плюс константный overhead — сходится.

O(n) — линейная сложность

Самый частый класс. Один проход по входу:

def total(lst):
    s = 0
    for x in lst:
        s += x      # n итераций
    return s

def find(lst, target):
    for x in lst:
        if x == target:
            return True
    return False

Любая встроенная функция sum, max, min, len(string) (для строки длины n) — O(n).

import timeit

setup = "lst = list(range(n))"
for n in [1_000, 100_000, 10_000_000]:
    t = min(timeit.repeat(
        'sum(lst)',
        setup=setup.replace('n', str(n)),
        number=100,
        repeat=5
    )) / 100
    print(f"n={n:>10}: {t*1000:.3f} ms")

Вывод:

n=      1000:  0.008 ms
n=    100000:  0.700 ms
n=  10000000: 75.000 ms

Рост в 10000 раз даёт рост времени примерно в 10000 раз. Это и есть O(n).

O(n log n) — линейно-логарифмическая

Появляется в эффективных алгоритмах сортировки и в задачах вида «для каждого элемента сделать log-операцию»:

def sort_them(lst):
    return sorted(lst)  # Timsort, O(n log n) worst case

def merge_intervals(intervals):
    intervals.sort()    # O(n log n)
    # ... дальше O(n)
    # итог: O(n log n)

Timsort в Python — гибридный алгоритм (merge sort + insertion sort). О нём отдельный модуль 15.

import timeit
import random

for n in [1_000, 100_000, 1_000_000]:
    setup = f"""
import random
random.seed(42)
lst = [random.random() for _ in range({n})]
"""
    t = min(timeit.repeat(
        'sorted(lst)',
        setup=setup,
        number=10,
        repeat=5
    )) / 10
    print(f"n={n:>10}: {t*1000:.2f} ms")

Вывод:

n=      1000:   0.10 ms
n=    100000:  16.00 ms
n=   1000000: 200.00 ms

Рост в 10 раз даёт рост примерно в 16 (для 1k -> 100k) и 12.5 (для 100k -> 1M). Это больше 10 (которое было бы для чистого O(n)), но меньше 100 (которое было бы для O(n²)) — то есть n log n.

O(n²) — квадратичная сложность

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

def naive_dedupe(lst):
    result = []
    for x in lst:           # внешний цикл O(n)
        if x not in result: # x not in result — O(n)
            result.append(x)
    return result            # итог: O(n) * O(n) = O(n^2)

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):       # O(n)
        for j in range(n-i-1):  # O(n)
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst                # итог: O(n^2)

Замер на разных n:

import timeit

for n in [100, 1000, 5000]:
    setup = f"""
def dedupe(lst):
    result = []
    for x in lst:
        if x not in result:
            result.append(x)
    return result
lst = list(range({n})) * 2
"""
    t = min(timeit.repeat('dedupe(lst)', setup=setup, number=3, repeat=3)) / 3
    print(f"n={n:>5}: {t*1000:.2f} ms")

Вывод:

n=  100:    0.4 ms
n= 1000:   30.0 ms
n= 5000:  750.0 ms

Рост n в 10 раз (100 -> 1000) дал рост времени в 75 раз — почти 100. Рост n в 5 раз (1000 -> 5000) — рост времени в 25 раз. Это квадратичный рост.

O(2^n) — экспоненциальная сложность

Появляется при переборе всех подмножеств, всех бинарных строк и подобных задачах. Каждый «лишний» элемент удваивает работу:

def all_subsets(lst):
    """Возвращает все 2^n подмножеств lst"""
    n = len(lst)
    result = []
    for mask in range(2**n):
        subset = [lst[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

На n=20 это уже миллион подмножеств. На n=30 — миллиард. На n=40 — триллион. Экспонента очень быстро становится нерабочей.

import timeit

for n in [10, 15, 20, 22]:
    setup = f"""
def all_subsets(lst):
    n = len(lst)
    result = []
    for mask in range(2**n):
        subset = [lst[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result
lst = list(range({n}))
"""
    t = min(timeit.repeat('all_subsets(lst)', setup=setup, number=1, repeat=3))
    print(f"n={n:>2}: {t*1000:>10.1f} ms, 2^n = {2**n}")

Вывод:

n=10:        2.0 ms, 2^n = 1024
n=15:       80.0 ms, 2^n = 32768
n=20:     3500.0 ms, 2^n = 1048576
n=22:    16000.0 ms, 2^n = 4194304

Удвоение n с 10 до 20 даёт рост времени в 1750 раз. С 20 до 22 (n+2) — в 4.5 раза (2² = 4, плюс overhead).

Попробуй сам: классифицируй код

# Что у этих функций по time complexity?

def f1(lst):
    return lst[-1]

def f2(lst):
    return [x*2 for x in lst]

def f3(lst):
    return sorted(lst, reverse=True)

def f4(lst):
    pairs = []
    for x in lst:
        for y in lst:
            if x != y:
                pairs.append((x, y))
    return pairs

def f5(n):
    if n <= 1:
        return n
    return f5(n-1) + f5(n-2)  # наивные Фибоначчи

Шпаргалка: какие операции какой сложности в Python

В следующем уроке — про space complexity: память тоже измеряется в big-O, и не всегда совпадает с time.