Какие знаешь вычислительные сложности алгоритмов

Временная сложность (Big O) показывает, как растёт время выполнения алгоритма с увеличением размера входных данных. Основные варианты:

• O(1) – константное время (доступ к элементу массива)

arr[0]  # O(1)

• O(log n) – логарифмическое (бинарный поиск)

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

• O(n) – линейное (поиск в неотсортированном массиве)

for x in arr:  # O(n)
    print(x)

• O(n log n) – (быстрая сортировка, сортировка слиянием)

sorted(arr)  # Timsort: O(n log n)

• O(n²) – квадратичное (пузырьковая сортировка)

for i in range(n):  # O(n²)
    for j in range(n):
        print(i, j)

• O(2ⁿ) – экспоненциальное (рекурсивный Фибоначчи без мемоизации)

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)  # O(2ⁿ)

Также есть пространственная сложность – потребление памяти. В реальных задачах важно учитывать оба типа сложности.