Основы 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 👩