Hacker News Digest

Big O — способ описать, как время работы функции растёт с ростом входных данных, без привязки к конкретным секундам.

Рассмотрим 4 основные категории:

---

O(n) — линейное время

function sum(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

• sum(1e9) ≈ 1 с
• sum(2e9) ≈ 2 с
  Время пропорционально n.

---

O(1) — константное время

function sum(n) {
  return (n * (n + 1)) / 2;
}

• sum(1e9) и sum(100e9) выполняются почти мгновенно.
  Время не зависит от n.

---

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

• O = «order of growth»; описывает рост, а не абсолютное время.
• O(1) ≠ «быстро», а «не растёт с размером входа».
• При достаточно большом n O(1) всегда обгонит O(n).

• Обсуждение статьи о нотации Big O разделилось на «лайтовое» восхищение визуализациями и «экспертные» споры о точности определений.
• Новички признаются, что статья впервые открыла им глаза на сложность алгоритмов, а ветераны IT спорят, что за 40 лет ни разу не пригодилась.
• Критика сводится к тому, что автор описывает «поп-культурный» вариант Big O, путая его с Θ-нотацией и worst-case.
• Практики напоминают: на реальном железе константы, кэш и NUMA могут перечеркнуть асимптотику, а O(n²) при малых n часто быстрее «константного» хэша.
• Люди делятся шпаргалками (bigocheatsheet.com, visualgo.net) и просят ещё интерактивных уроков.

Что такое «Busy Beaver»
Функция Σ(n) показывает максимальное количество 1, которое может оставить на ленте останавливающаяся машина Тьюринга с n состояниями и двумя символами (0 и 1). Аналогично, S(n) — максимальное число шагов до остановки. Оба значения растут быстрее любой вычислимой функции, поэтому уже Σ(5) и S(5) неизвестны без компьютерного перебора.

Новый рекорд: n = 6
Команда «Beaver Hunters» (Scott Aaronson, Shawn Ligocki et al.) доказала:

• S(6) = 36 534 678 263 377 ≈ 3,65 × 10¹³
• Σ(6) = 10 ↑↑ 15
  (15-я степень десятки в стеке степеней: 10^(10^(10^…)))

Это число настолько велико, что его нельзя записать в обычной десятичной форме: для этого потребовалось бы больше атомов, чем во Вселенной.

Как нашли

• Использовали SAT-решатели и распределённые вычисления, чтобы перебрать ~10⁴⁴ машин.
• Для оставшихся «подозрительных» случаев построили индивидуальные доказательства остановки или бесконечного цикла.
• Работа заняла ~2 года и миллионы часов CPU.

Зачем это нужно

• Busy Beaver служит «натуральной» границей между вычислимым и не-вычислимым.
• Новые методы перебора и доказательств могут пригодиться в верификации ПО и теории сложности.
• Следующая цель — n = 7, но она потребует принципиально новых идей и, вероятно, ещё более фантастических чисел.

• Участники обсуждают сверхбольшие конечные числа: Busy Beaver, TREE(3), субкубические графы и быстро-растущие иерархии.
• BB-функция растёт быстрее любой вычислимой функции и не вычислима; для N>549 нельзя доказать в ZFC, что какое-то вычислимое число ≥BB(N).
• Поделились ссылками на видео Numberphile, плейлист Дэвида Мецлера и статью Скотта Ааронсона.
• Появились размышления о том, что делает такие числа интереснее бесконечности, а также о состоянии ленты после остановки BB(5).
• Некоторые критикуют статью Quanta за поверхностное описание экспоненциации и отсутствие объяснения сути BB.