Операторы и big-O / amortized analysis

Big-O — единственный способ сравнивать алгоритмы независимо от железа: процессор, кэш, частота, компилятор могут менять абсолютное время в десятки раз, но не порядок роста. Amortized analysis — способ оценить операции с distribution: list.append иногда O(n) (на realloc’е), но «в среднем» O(1) — потому что дорогие операции редкие, а каждая из них «оплачивает» работой все следующие дешёвые.

Это первокласная тема для data engineer’а: понимание amortized O(1) для list.append и dict.__getitem__ объясняет, почему pandas/Polars быстрее наивного Python, и где ваш код становится квадратичным «случайно».

Big-O notation: формальное определение

f(n) = O(g(n)) означает: ∃ константы c > 0 и n₀ ≥ 0 такие, что для всех n ≥ n₀ выполняется |f(n)| ≤ c · |g(n)|. Это upper bound — функция растёт не быстрее, чем g(n), начиная с какого-то размера.

• Big-Θ (theta) — tight bound: одновременно O(g) и Ω(g).
• Big-Ω (omega) — lower bound: f растёт не медленнее, чем g.

На практике в Python community говорят «O» имея в виду Θ — это слабее формально, но обычно понятно из контекста («dict.get это O(1)» означает Θ(1) average-case, а worst-case Θ(n)).

Big-O для основных операций Python

Реальные сложности (см. docs.python.org/3/library/stdtypes.html и TimeComplexity wiki):

Ключевые наблюдения:

• x in list — O(n), а x in set/dict — O(1) avg. Если фильтруете большой список — сначала постройте set(haystack) за O(n), потом множественные x in set каждый O(1). Без этого получите классический O(n·m) anti-pattern.
• list.insert(0, x) — O(n), а list.append(x) — amortized O(1). Если строите коллекцию через front-prepend — используйте collections.deque (O(1) на обоих концах).
• dict.__getitem__ — O(1) avg, но worst-case O(n) при намеренных коллизиях. Поэтому CPython с 3.4 использует randomized hash для str/bytes (см. PYTHONHASHSEED).

Amortized analysis — list.append на примере

list — contiguous массив PyObject* с capacity ≥ length. Поле ob_item — указатель на массив, allocated — capacity, ob_size — length. См. Objects/listobject.c.

Append работает так:

1. Если allocated > ob_size — просто пишем pointer в ob_item[ob_size], инкрементируем ob_size. O(1).
2. Если allocated == ob_size — вызываем list_resize: аллоцируем новый массив большего размера (new_allocated), копируем все указатели, освобождаем старый. O(n).

Геометрический рост: list_resize использует формулу

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

Это означает: новый capacity ≈ newsize + newsize/8 + 6, округлённый до multiple-of-4. Фактор роста ~1.125x — баланс между memory waste и частотой realloc.

Aggregate analysis для n appends подряд (от пустого list):

• Дешёвых append’ов: ~n
• Дорогих realloc’ов: log_1.125(n) ≈ 8.5 · log(n) штук (для n=1000 — ~26 realloc’ов)
• Суммарная работа всех realloc’ов: 1 + 1.125 + 1.266 + … ≤ n / (1 - 1/1.125) = 9n
• Итого ≤ n + 9n = O(n)
• Average per append = O(n) / n = O(1).

import sys

# Реальные размеры из baseline (cpython-3.12.7):
# len=0  → 56 байт   (header только, capacity=0)
# len=1  → 72 байт   (capacity≈4)
# len=4  → 88 байт   (capacity≈8)
# len=8  → 120 байт  (capacity≈16)
# len=16 → 184 байт  (capacity≈25)
# len=32 → 312 байт  (capacity≈37)
lst = []
for i in range(33):
    print(len(lst), sys.getsizeof(lst))
    lst.append(None)

Видно ступеньки: размер не растёт на каждом append’е, а скачет на realloc’ах.

Зачем именно geometric reallocation

Если бы capacity рос на +1 каждый раз (linear), для n appends получили бы:

• Total work = 1 + 2 + 3 + … + n = n(n+1)/2 = O(n²)
• Per append = O(n) (а не O(1))

Вы делали бы по миллиарду операций на миллион append’ов. Catastrophic.

Geometric (factor c > 1) даёт total work = O(n), а per append = O(1) amortized. Чем больше c, тем меньше realloc’ов, но больше memory overhead. CPython выбрал c ≈ 1.125 — компромисс. Java ArrayList — 1.5. Go slice — 2.0 (меньше n=1024) затем 1.25.

Cite: CLRS глава 17 — Amortized Analysis, три метода (aggregate, accounting, potential).

Когда big-O вводит в заблуждение

O(1) для dict lookup — это amortized average, а не worst-case. Worst-case (все ключи коллидят в одно ведро) — O(n). Для security-critical паттерна (DoS via hash collision) Python с 3.4 использует randomized hash для str/bytes:

import sys
print(sys.hash_info)  # algorithm='siphash13', hash_bits=64
# PYTHONHASHSEED=random (по умолчанию): рандомизация при старте процесса
# PYTHONHASHSEED=0: детерминированный hash (для тестов; не использовать в проде)

См. SipHash в Python/pyhash.c. Атакующий не может предсказать, какие строки коллидят, потому что seed случаен на каждый запуск.

Big-O скрывает константы. Кэш-friendly алгоритм с O(n²) часто бьёт cache-hostile O(n log n) на n до 10000 (типичные размеры). Реальная производительность = асимптотика × константа × cache locality. Для серьёзных оптимизаций — профилируйте, не теоретизируйте.

Cross-course context

Ключевые выводы

1. Big-O — upper bound, не учитывает константы; для real perf — benchmarking с реальными данными.
2. Amortized = average over sequence of operations; ключевая идея для list.append (O(1) amortized, O(n) worst), dict resize, многих других.
3. CPython list_resize использует geometric growth с factor ~1.125 — компромисс между memory waste и частотой realloc. См. Objects/listobject.c.