Алгоритмічна складність

Наскрізний хребет каналу: складність — це те, як обсяг роботи росте з розміром входу, незалежно від швидкості мови. Фірмова ілюстрація Віктора — сила log N: 50 рядків лінійно — це 50 кроків, але 100 трильйонів рядків — лише ~46 кроків бінарного пошуку; «log N — це практично безплатно» (навіщо потрібні індекси, індекси в MySQL і Postgres, дерева й алгоритми пошуку). Зворотний бік, який він завжди додає: вставка у відсортований масив — це O(N), і саме в цьому вся мотивація деревоподібних структур (дерева й алгоритми пошуку).

Його наочний доказ — приклад зі злиттям повідомлень: зʼєднання 2000 повідомлень зі 100 користувачами через вкладений find коштує ~200 000 операцій; попередня побудова хеш-мапи зрізає це до ~2100 (O(n*m) → O(n+m)). Константи теж важать: чистий JS-бінарний пошук (O(log n)) на масштабі обганяє реалізований на C++ Array.includes (O(n)), а розрив ~23x між find та includes показує, що константи реалізації реальні — але асимптотику вони не переможуть ніколи (навіщо алгоритми). Та сама оптика проходить крізь бенчмарки фільтра Блума: повний скан проти індексу, проти памʼяті, проти фільтра — це про порядки величин, а не тюнінг конфігів: «нас цікавить порядок цифр» (фільтр Блума і Firefox).

Його карʼєрний висновок: алгоритми руками пишеш рідко, але аналізувати складність мусиш — на код-ревʼю він регулярно виловлює O(n²) і кубічні гарячі точки, просто читаючи код. Бойова історія: рушій «Excel на JS» довелося переписати — топологічне сортування ітеративно, із саморобним стеком, — бо ліміт JS у ~10k стекових фреймів ламався на ланцюжках залежностей, довших за 10k клітинок (Q&A №2). Розділ про аналіз складності в Cracking the Coding Interview він виокремлює як одну з двох по-справжньому цінних частин цієї книжки (книжки на пʼять зірок).