big-o-cheatsheet.js·4 scenarios
Big-O Cheatsheet for System Design — interactive concept page that visualizes complexity classes (O(1), O(log n), O(n), O(n log n), O(n²), O(2^n)) through node load sizes and capacity caps. Compares HashMap vs sorted array vs linked list lookup, B-tree vs LSM with Bloom filter, and brute-force kNN vs HNSW vs IVF+PQ. Includes 4 scenarios: lookup comparison at N=1B, sort comparison (mergesort vs bubble), disk indices (B-tree vs LSM+Bloom), and ANN with exponential warning. ADR explains when NOT to optimize complexity (small N, IO-bound, cache locality, rare execution).
Big-O — самая «школьная» тема, которую системные архитекторы недооценивают. На leetcode-собеседовании это про сортировку массивов. В реальном дизайне распределённой системы это другой вопрос: «можно ли так искать в индексе на 1B записей?», «сэкономит ли Bloom filter миллион disk seeks в день?», «kNN brute-force на 1M векторов — это 5 секунд или 5 миллисекунд?».
Big-O для системного дизайна — это не теория, а рабочий справочник из 30 чисел, которые архитектор использует при выборе data structure, индекса или алгоритма. Без него выбор «B-tree vs LSM», «HashMap vs sorted array», «brute kNN vs HNSW» сводится к карго-культу. С ним — к расчёту: «B+ tree с B=200 на 1B = 4 disk seeks = 40ms, нас устроит».
Это второй уровень после [CONCEPT]numbers-to-know (latency-numbers Jeff Dean). Numbers-to-know отвечают на «сколько стоит одна операция». Big-O — на «как стоимость растёт с N».
«В системе важна не только asymptotic O(...), но и константа (cache miss = 100ns, disk seek = 10ms — разница в 100,000×) и база логарифма (B-tree O(log_B N) с B=200 даёт 4 уровня для 1B; binary search O(log_2 N) — 30. Та же асимптотика, но в 7.5× медленнее).»
Три правила, которые ломают наивное «O() — это всё, что нужно знать»:
std::sort и Python Timsort переключаются на insertion sort ниже порога. CPython linear scan list из 100 элементов быстрее dict из-за hash-overhead.Best big-O в asymptotic смысле может проиграть худшему, если делает больше disk seeks или ломает cache locality.
Шесть групп на канвасе — это визуальная шпаргалка из шести категорий:
Группа «Complexity classes» — лестница из 6 нод, показывающая стоимость каждого класса для N=1B:
o1 (O(1) · 1 op · HashMap, array index)ologn (O(log n) · 30 ops · BST, B-tree, binary search)on (O(n) · 1B ops · linear scan, linked list)onlogn (O(n log n) · 30B ops · mergesort, quicksort)on2 (O(n²) · 1e18 ops · brute kNN, nested loop) — state: degradedo2n (O(2^n) · heat death · subset sum, naive TSP) — state: failedЦветовая семантика (green/yellow/red glow) сразу показывает, какие классы приемлемы на проде, а какие — это «уйдёт за пределы вселенной».
Группа «Lookup: HashMap vs Sorted Array vs Linked List» — три структуры в памяти с одинаковой задачей find key=42. HashMap O(1) avg, sorted array O(log N), linked list O(N). Edges от клиента подписаны: get(k), bsearch, walk.
Группа «Disk-based indices» — четыре дисковые структуры для 1B записей: B+ tree, LSM tree, Bloom filter, inverted index. Edge lsm → bloom отдельный — показывает, что Bloom — оптимизация поверх LSM.
Группа «kNN: Brute-force vs HNSW» — три алгоритма ANN на 1M × 768-dim векторах: brute kNN O(N×D) (red, fails), HNSW O(log N) (green), IVF+PQ O(√N) (green).
Клиент-нода client слева — отправляет запросы в каждую группу через edges с подписями типа lookup, index, scan, sort, seek. Это не «реальный путь данных» — это визуальное «куда мог бы пойти запрос, если бы мы выбрали этот тип индекса».
Capacity hints (maxRps) на каждой ноде заданы в соответствии с реальным throughput: HashMap 100K rps, B-tree 10K, brute kNN 1 rps. Это даёт калькулятору ёмкости подсказку, какой будет загрузка.
Четыре сценария в FlowBuilder, переключаемых через scenario-pills в плеере:
lookup-comparison — «Lookup: O(1) vs O(log n) vs O(n)»: запрос find key=42 в N=1B одновременно идёт в HashMap (100ns), sorted array (3µs), linked list (10s). flashError на linked list, финальный showMessage: «HashMap 30M× быстрее linked list на N=1B».
sort-comparison — «Sort: O(N log N) vs O(N²)»: mergesort 1M элементов = 20ms, bubble sort 1M = 16 минут. Caveat: insertion sort бьёт quicksort на N<32 (Timsort/std::sort это знают). External merge sort для N > RAM.
disk-indices — «B-tree vs LSM + Bloom»: log_200(1B)=4 уровня = 4 seeks = 40ms (B+ tree). LSM write O(1) amortized → Bloom отсекает 95% bogus reads → 1 SSTable seek 10ms. Финал: «та же O(log N), разные константы: B-tree 40ms vs binary search 300ms vs HashMap 100ns».
ann-and-exponential — «ANN: brute-force vs HNSW · O(2^n) warning»: brute kNN 1M×768 dims = 4GB scan/query = 5 секунд (классическая ошибка «работало на 1K, ляжет на 1M»). HNSW O(log N) = 5ms @ 97% recall. IVF+PQ O(√N) = 10ms + 4× компрессия. Затем O(2^N) warning: N=60 для subset sum дольше возраста вселенной. Финал: HashMap collision DoS-атака → O(N) → fix via random seed.
На ноде o2n зашит ADR-001 «Когда НЕ нужно оптимизировать сложность» — он раскрывает контр-интуитивную часть Big-O:
Контекст: каждый второй интервью-вопрос — про «уменьши big-O». В реальности константа важнее: алгоритм с худшей асимптотикой и лучшим cache locality бьёт асимптотически лучший конкурент на малых N. Constant factor дисковых seeks (10ms) делает O(log N) на B-tree (B=200, 4 уровня = 40ms) драматически быстрее O(log N) на binary search массива (30 уровней = 300ms).
Решение: не оптимизируй complexity, если: (1) N ограничен сверху и мал (<1K) — O(N²) приемлемо, читать проще; (2) узкое место — IO/network, не CPU (профилируй сначала); (3) cache locality важнее асимптотики (массив бьёт linked list даже при O(N) vs O(1) insert); (4) код выполняется редко (cron раз в день). Оптимизируй: на горячем пути, при N → ∞, при адверсариальном инпуте (DoS через collision), при работе с диском (Bloom filter перед SSTable read).
SET/GET) O(1), sorted set = skip list + hash table hybrid O(log N), HyperLogLog (PFCOUNT) O(1) cardinality estimate в 12KB на любой N.Не оптимизируй big-O, когда:
flamegraph, perf).Не доверяй Big-O вслепую:
Не выбирай structure по теоретической complexity без бенчмарка на ваших данных, паттернах доступа, размере N, и hardware. BTreeMap vs HashMap в Rust на 10K элементов: разница в разы в обе стороны в зависимости от key-distribution.