Big O Notation: временная сложность алгоритмов на примерах Python

# Big O Notation: временная сложность алгоритмов на примерах Python Big O — это способ описать, **как растёт время работы алгоритма при увеличении размера входных данных**. Важно понимать: Big O показывает именно **скорость роста**, а не абсолютное время выполнения программы. То есть алгоритм с `O(1)` не обязательно выполняется мгновенно. Это означает лишь, что его сложность не увеличивается вместе с размером входных данных. Обычно размер входных данных обозначают как `n`. --- ## 1. Constant Time — O(1) **Константная сложность — `O(1)`** Время работы алгоритма остаётся постоянным и не зависит от размера входных данных. Например, если мы обращаемся к элементу массива по известному индексу, нам не нужно перебирать весь массив. ### Примеры ```python # Array nums = [1, 2, 3] nums.append(4) # push to end nums.pop() # pop from end nums[0] # lookup nums[1] nums[2] ``` В примере выше показаны: - добавление элемента в конец массива; - удаление элемента с конца; - обращение к элементу по индексу. Также в PDF приведён пример с `HashMap`: ```python # HashMap / Set hashMap = {} hashMap["key"] = 10 # insert print("key" in hashMap) # lookup print(hashMap["key"]) # lookup hashMap.pop("key") # remove ``` Основная идея `O(1)`: ```text Размер входных данных увеличивается, но количество выполняемых действий не растёт. ``` --- ## 2. Logarithmic Time — O(log n) **Логарифмическая сложность — `O(log n)`** Время работы алгоритма растёт логарифмически относительно размера входных данных. Типичный пример — **Binary Search**. При бинарном поиске после каждой проверки область поиска существенно уменьшается. ### Binary Search ```python # Binary search nums = [1, 2, 3, 4, 5] target = 6 l, r = 0, len(nums) - 1 while l nums[m]: l = m + 1 else: print(m) break ``` На каждой итерации мы выбираем середину: ```python m = (l + r) // 2 ``` После этого продолжаем поиск только слева или только справа. То есть вместо последовательного просмотра всех элементов область поиска постоянно сокращается. ### Binary Search в BST В PDF также приведён поиск по бинарному дереву: ```python # Binary Search on BST def search(root, target): if not root: return False if target root.val: return search(root.right, target) else: return True ``` На каждом шаге поиск продолжается только в одной части дерева. ### Heap Push и Pop Ещё один пример: ```python # Heap Push and Pop import heapq minHeap = [] heapq.heappush(minHeap, 5) heapq.heappop(minHeap) ``` Операции добавления и удаления элемента из heap в приведённой шпаргалке относятся к `O(log n)`. --- ## 3. Linear Time — O(n) **Линейная сложность — `O(n)`** Время работы алгоритма растёт линейно вместе с размером входных данных. Если алгоритму необходимо обработать каждый элемент массива, обычно мы получаем `O(n)`. ### Примеры ```python nums = [1, 2, 3] sum(nums) # sum of array for n in nums: # looping print(n) ``` Чтобы получить сумму массива, необходимо обработать его элементы. То же самое происходит при обычном проходе: ```python for n in nums: print(n) ``` В PDF также приведены операции: ```python nums.insert(1, 100) # insert middle nums.remove(100) # remove middle print(100 in nums) # search ``` И построение heap: ```python import heapq heapq.heapify(nums) # build heap ``` ### Важное замечание В PDF отдельно отмечено: ```text sometimes even nested loops can be O(n) (e.g. monotonic stack or sliding window) ``` То есть наличие вложенного цикла **само по себе ещё не означает `O(n²)`**. Нужно смотреть на то, сколько операций реально выполняется относительно размера входа. --- ## 4. Square Root Time — O(√n) **Сложность порядка квадратного корня — `O(√n)`** Время работы алгоритма растёт как квадратный корень из размера входных данных. В PDF в качестве примера используется поиск всех делителей числа. ```python # Get all factors of n import math n = 12 factors = set() for i in range(1, int(math.sqrt(n)) + 1): if n % i == 0: factors.add(i) factors.add(n // i) ``` Мы перебираем значения только до: ```python math.sqrt(n) ``` Если нашли один делитель: ```python i ``` то сразу можем получить второй: ```python n // i ``` Поэтому полный перебор от `1` до `n` не требуется. --- ## 5. Loglinear Time — O(n log n) **Линейно-логарифмическая сложность — `O(n log n)`** Такая сложность сочетает линейный и логарифмический рост. Типичный пример — эффективные алгоритмы сортировки. ### HeapSort ```python # HeapSort import heapq nums = [1, 2, 3, 4, 5] heapq.heapify(nums) # O(n) while nums: heapq.heappop(nums) # O(logn) ``` Сначала создаётся heap: ```python heapq.heapify(nums) ``` В примере его сложность обозначена как: ```text O(n) ``` Затем элементы извлекаются: ```python heapq.heappop(nums) ``` Стоимость одной такой операции: ```text O(log n) ``` А выполнять её необходимо для элементов массива. В PDF также отмечено: ```text MergeSort (and most built-in sorting functions) ``` как пример алгоритмов с характерной сложностью `O(n log n)`. --- ## 6. Bilinear Time — O(n * m) **Билинейная сложность — `O(n * m)`** Такая сложность возникает, когда алгоритм работает с двумя независимыми размерами данных. Например: ```text n — количество элементов первого массива m — количество элементов второго массива ``` И для каждого элемента первого массива необходимо обработать каждый элемент второго. ### Все пары из двух массивов ```python # Get every pair of elements from two arrays nums1, nums2 = [1, 2, 3], [4, 5] for i in range(len(nums1)): for j in range(len(nums2)): print(nums1[i], nums2[j]) ``` Внешний цикл выполняется `n` раз. Внутренний — `m` раз для каждой итерации внешнего. Получаем: ```text O(n * m) ``` ### Обход прямоугольной матрицы ```python # Traverse rectangle grid nums = [[1, 2, 3], [4, 5, 6]] for i in range(len(nums)): for j in range(len(nums[i])): print(nums[i][j]) ``` Если имеется `n` строк и `m` столбцов, нужно обработать: ```text n * m ``` элементов. --- ## 7. Quadratic Time — O(n²) **Квадратичная сложность — `O(n²)`** Время работы растёт квадратично относительно размера входных данных. Обычно это происходит, когда выполняется примерно: ```text n * n ``` операций. Например, вложенный цикл по одной и той же коллекции. ### Обход квадратной матрицы ```python # Traverse a square grid nums = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] for i in range(len(nums)): for j in range(len(nums[i])): print(nums[i][j]) ``` ### Получение всех пар элементов ```python # Get every pair of elements in array nums = [1, 2, 3] for i in range(len(nums)): for j in range(i + 1, len(nums)): print(nums[i], nums[j]) ``` В PDF также упоминается: ```text Insertion sort (insert in middle n times -> n^2) ``` ### Два последовательных цикла — это не O(n²) Это важный момент из PDF. Если мы два раза отдельно прошли массив: ```python for n in nums: print(n) for n in nums: print(n) ``` сложности складываются: ```text O(n) + O(n) ``` Получаем: ```text O(2n) ``` В Big O константа отбрасывается: ```text O(n) ``` Поэтому: ```text O(n) + O(n) = O(n) ``` а **не**: ```text O(n²) ``` --- ## 8. Cubic Time — O(n³) **Кубическая сложность — `O(n³)`** Время выполнения растёт кубически относительно размера входа. В PDF показан пример получения всех троек элементов массива. ```python # Get every triplet of elements in array nums = [1, 2, 3] for i in range(len(nums)): for j in range(i + 1, len(nums)): for k in range(j + 1, len(nums)): print(nums[i], nums[j], nums[k]) ``` Здесь используется три уровня перебора. В общем случае такой рост обозначается: ```text O(n³) ``` При увеличении `n` количество операций начинает расти очень быстро. --- ## 9. Exponential Time — O(2ⁿ) **Экспоненциальная сложность — `O(2ⁿ)`** Время выполнения алгоритма растёт экспоненциально относительно размера входных данных. Такое часто можно встретить в рекурсивных алгоритмах, где каждый вызов порождает несколько новых вызовов. ### Рекурсия с двумя ветвями В PDF приведён следующий пример: ```python # Recursion, tree height n, two branches def recursion(i, nums): if i == len(nums): return 0 branch1 = recursion(i + 1, nums) branch2 = recursion(i + 2, nums) ``` Идея заключается в построении дерева рекурсивных вызовов. Один вызов создаёт новые ветви, затем каждая из них создаёт следующие. В PDF такой тип роста приводится как пример экспоненциальной сложности. ### O(cⁿ) Также в изображении есть обобщённый вариант: ```python # c branches, where c is sometimes n. def recursion(i, nums, c): if i == len(nums): return 0 for j in range(i, i + c): branch = recursion(j + 1, nums) ``` Если каждый уровень рекурсии создаёт `c` новых ветвей, рост можно представить как: ```text O(cⁿ) ``` В PDF отдельно указано, что экспоненциальная сложность часто встречается в деревьях решений вида: ```text include / exclude ``` Например, при генерации всех подмножеств из `n` элементов. --- ## 10. Factorial Time — O(n!) **Факториальная сложность — `O(n!)`** Время работы алгоритма растёт факториально вместе с размером входных данных. Такой тип сложности часто возникает при генерации **всех перестановок `n` различных элементов**, когда имеет значение порядок элементов. ### Генерация перестановок Код из PDF: ```python # Permutations def permute(nums): def backtrack(path, nums): if not nums: res.append(path) return for i in range(len(nums)): backtrack( path + [nums[i]], nums[:i] + nums[i + 1:] ) res = [] backtrack([], nums) return res ``` Алгоритм по очереди выбирает каждый доступный элемент и рекурсивно строит все возможные варианты расположения оставшихся элементов. Именно поэтому количество вариантов растёт факториально. --- # Как выглядят сложности рядом От наиболее медленного роста к наиболее быстрому: ```text O(1) O(log n) O(√n) O(n) O(n log n) O(n * m) O(n²) O(n³) O(2ⁿ) O(n!) ``` При этом `O(n * m)` нельзя напрямую поставить в одно фиксированное место относительно `O(n²)`, не зная отношения между `n` и `m`. Если: ```text m = n ``` то: ```text O(n * m) = O(n²) ``` --- # Как распознавать Big O в коде Упрощённая памятка: ```text Обращение к конкретному элементу → O(1) На каждом шаге область поиска уменьшается → O(log n) Один проход по коллекции → O(n) Перебор до √n → O(√n) n операций, каждая стоимостью log n → O(n log n) Вложенные циклы по двум независимым коллекциям → O(n * m) Вложенные проходы по данным размера n → O(n²) Три уровня перебора → O(n³) Рекурсивное дерево с несколькими ветвями → O(2ⁿ) или O(cⁿ) Перебор всех перестановок → O(n!) ``` --- # Главное о Big O Big O измеряет **скорость роста сложности алгоритма при увеличении размера входных данных**, а не его абсолютную скорость. Поэтому: ```text O(1) ``` не означает: ```text «программа обязательно работает быстро» ``` Это означает: ```text «количество работы не растёт вместе с размером входных данных» ``` При анализе алгоритма важно смотреть не просто на количество строк или циклов, а на то, **как количество выполняемых операций зависит от `n`**.