Постараюсь ввести вас в курс дела как аналитиков, потому что любое 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 👩