Big O — это способ описать, как растёт стоимость алгоритма при увеличении
размера входных данных.
Чаще всего говорят о времени:
O(1)
O(log n)
O(n)
O(n log n)
O(n^2)
Но важно: O(...) само по себе не означает «худший случай».
O(...) описывает рост функции. А вот какую именно функцию мы анализируем,
нужно уточнять:
worst-case time
average-case time
best-case time
expected time
amortized time
space complexity
То есть можно сказать:
worst-case O(n)
average-case O(1)
expected O(1)
amortized O(1)
space O(n)
В алгоритмических задачах, особенно на собеседованиях, когда просто говорят:
this algorithm is O(n)
обычно по умолчанию имеют в виду worst-case time complexity.
Но это соглашение контекста, а не свойство Big O как математической записи.
Правильнее мыслить так:
Big O — это верхняя оценка роста для выбранного режима анализа.
Можно анализировать разные режимы:
worst-case O(n^2)
average-case O(n log n)
best-case O(n)
amortized O(1)
expected O(1)
Где возникает путаница
Классический пример — hash map и hash set.
Когда говорят:
HashMap lookup is O(1)
это почти всегда сокращённая фраза. Полная версия:
HashMap lookup is O(1) on average / expected case
А в худшем случае lookup в hash map может быть:
O(n)
Потому что все ключи теоретически могут попасть в одну и ту же корзину из-за
hash collision.
Пример с hash buckets
Допустим, hash map внутри имеет корзины:
bucket 0
bucket 1
bucket 2
bucket 3
Нормальная ситуация:
bucket 0: [apple]
bucket 1: [cat]
bucket 2: [dog]
bucket 3: [sun]
Тогда lookup быстрый:
hash("dog") -> bucket 2 -> нашли
Это выглядит как O(1).
Плохая ситуация:
bucket 0: [apple, cat, dog, sun, table, car, ...]
bucket 1: []
bucket 2: []
bucket 3: []
Теперь hash привёл всех в одну корзину, и внутри этой корзины нужно искать среди
многих элементов.
Тогда lookup превращается примерно в:
O(n)
HashMap lookup
Для обычной hash map или hash set точная формулировка такая:
lookup: average / expected O(1)
lookup: worst-case O(n)
Для Java HashMap есть дополнительная защита: когда в одной корзине становится
слишком много элементов, Java может превратить цепочку в дерево. Тогда худший
случай для этой корзины становится ближе к:
O(log n)
Но в алгоритмических задачах обычно всё равно говорят проще:
HashMap / HashSet lookup is O(1) average case
Почему на LeetCode всё равно пишут O(1)
Потому что для большинства задач предполагается нормальная hash function и
нормальное распределение ключей.
Например:
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
Технически:
x in seen -> average O(1), worst-case O(n)
Но весь алгоритм обычно записывают как:
Time: O(n)
Space: O(n)
Потому что берут ожидаемую нормальную работу hash set.
Amortized complexity
Amortized complexity описывает среднюю стоимость операции в длинной серии
операций, даже если отдельная операция иногда дорогая.
Пример — динамический массив.
Обычно push в конец работает за:
O(1)
Но иногда массиву нужно выделить новый блок памяти и скопировать старые
элементы. Такая отдельная операция может стоить:
O(n)
При этом за длинную последовательность добавлений средняя стоимость одного
push остаётся:
amortized O(1)
Space complexity
Big O используют не только для времени, но и для памяти.
Например:
seen = set(nums)
По времени это обычно:
Time: O(n)
По памяти:
Space: O(n)
Потому что мы создаём дополнительную структуру, которая в худшем случае хранит
все элементы.
Главное различение
Big O — это не обязательно худший случай.
Big O — это верхняя оценка роста для выбранного режима анализа.
Поэтому правильно говорить так:
HashMap lookup не "абсолютно O(1)".
HashMap lookup — O(1) в среднем / ожидаемо.
В худшем случае может быть хуже.
В собеседовательном контексте, если ничего не уточняют, часто подразумевают
worst case. Но с hash-структурами есть устоявшееся сокращение: говорят O(1),
подразумевая average / expected case.
