Основы O-оценки сложности для алгособесов

Постараюсь ввести вас в курс дела как аналитиков, потому что любое Leetcode-собеседование (а их становится больше) подразумевает если не совсем оптимальное решение, то что кандидат хотя бы понимает, как это измеряется

Что это вообще такое?
Big-O («О большое») — это асимптотическая* оценка того, c какой скоростью растут время и/или память алгоритма при увеличении размера входных данных, если отбросить константы
* для подробностей нужно определение предела, не сегодня

Время в данном случае — это количество простейших операций (что-нибудь сложить, умножить, присвоить), память — количество переменных, которое приходится хранить (например, во вспомогательных массивах), размер входа — сколько данных нам дано. Например, даётся один массив чисел — его длину мы обозначаем за N. Может быть задача, где каждый элемент входного массива уже не просто число, а, например, строка длины не более M, и это тоже окажется важно...

Основные правила оценки сложности вашего кода
Учим, как аксиомы:
Любые фиксированные присвоения переменных (например, инициализация какой-нибудь суммы или указателей-индексов) — это константная сложность O(1)
Линейный проход по всем элементам массива — O(N)
Сортировка — O(N log N), если встроенная и оптимальная, но иногда доходит до O(N^2) (это уже другая история)
Вложенные циклы: сложности перемножаются. Если у вас 2 вложенных for i in arr, где arr — ваш входной массив длины N, то будет O(N^2), если 3 — то O(N^3), и так далее...

Если массива два, то будет O(N * M), пример:

for i in range(len(arr_1)): # arr_1 - массив длины N

    for j in range(len(arr_2)): # arr_2 - массив длины M

        ...

У последовательных шагов сложности складываются, но более быстрорастущее слагаемое поглощает остальные. То есть, если у вас сначала один цикл обработки массива, а потом 2 вложенных, то в пределе не O(N^2) + O(N), а просто O(N^2).

Если циклы не вложенные по двум массивам, то мы оставляем O(N + M), потому что не можем сравнить N и M асимптотически.

Быстрый порядок величин «от лучше к хуже»:
O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N) < O(N!)

До последних двух мы стараемся не доходить в задачах на собесах, это нереально много операций. Например, задача рандомной перестановки элементов массива не подразумевает, что вы сгенерируете все N! штук, сохраните их и выберете.

Библиотечные методы и структуры тоже учитываются
Они оптимизированы по мере возможности, но та же сортировка никогда не станет линейной Продвинутый уровень — выучить, что оптимально для какой операции.

Пример фразы, которая растопит сердце интервьюера

Тут получается сложность O(N) за счёт линейного поиска по массиву, инициализация переменных была за O(1). Могу написать бинпоиск, будет оптимальнее — за O(log N)...

Особенно, если вы реально понимаете, почему так работает))

Буду ждать фидбек, стало ли понятнее И пересылайте друзьям, которые собираются на стажировки и другие собесы!

#хардов_пост #найм_и_собесы
@analytess