Что такое нотация Big-O и зачем она нужна?

Junior PRO

Суть

Big-O описывает, как растёт время работы (или память) алгоритма при росте размера входа n. Константы и младшие члены отбрасываются: O(2n + 10) — это O(n). По умолчанию говорят о худшем случае; для Array.append и хеш-таблиц важно уточнять «амортизированно» и «в среднем».

Классы по возрастанию:

• O(1) — доступ по индексу, Dictionary lookup в среднем.
• O(log n) — бинарный поиск, сбалансированное дерево.
• O(n) — линейный проход, contains у массива.
• O(n log n) — хорошие сортировки, sort() в Swift.
• O(n²) — вложенные циклы по одной коллекции.
• O(2ⁿ) — наивная рекурсия (Фибоначчи), полный перебор подмножеств.