Какие знаешь методы оценки сложности алгоритма?

# Методы оценки сложности алгоритма

Оценка сложности — это один из самых важных навыков для разработчика. Она позволяет предсказать, как алгоритм поведёт себя при больших объёмах данных.

1. Big O (О-большое) — асимптотическая нотация

Big O показывает верхнюю границу времени выполнения в худшем случае.

Основные классы сложности (от быстрого к медленному)

Визуальное представление

    ↑ Время выполнения
    │
    │        O(n!)
    │      O(2ⁿ)
    │    O(n³)
    │   O(n²)
    │  O(n log n)
    │ O(n)
    │O(log n)
    │O(1)
    └───────────→ Размер входных данных (n)

2. Как считать сложность

Правило 1: Отбрасываем константы

# O(5n + 10) = O(n)
# O(2n²) = O(n²)
# O(100) = O(1)

def process_data(arr):
    x = arr[0]      # O(1)
    y = arr[1]      # O(1)
    for i in arr:   # O(n)
        print(i)    # O(1)
    # Итого: O(1) + O(1) + O(n) + O(n) = O(n)

Правило 2: Берём самый медленный шаг

def mixed_complexity(arr):
    for i in arr:           # O(n)
        print(i)
    
    for i in arr:           # O(n)
        for j in arr:       # O(n) вложенный
            print(i, j)     # O(1)
    # Итого: O(n) + O(n²) = O(n²) — берём самый медленный

Правило 3: Вложенные циклы перемножаются

def nested_loops(matrix):
    for row in matrix:      # n итераций
        for col in row:     # m итераций
            process(col)    # O(1)
    # Итого: O(n * m) = O(n²) если n = m

3. Примеры анализа популярных алгоритмов

Линейный поиск

def linear_search(arr, target):
    for i in range(len(arr)):  # n итераций в худшем случае
        if arr[i] == target:
            return i
    return -1
# Сложность: O(n)

Бинарный поиск

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:  # Делим пополам: log n итераций
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
# Сложность: O(log n)

Пузырьковая сортировка

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):          # n итераций
        for j in range(n - i - 1):  # n итераций (вложенный)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
# Сложность: O(n²)

Быстрая сортировка (QuickSort)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]     # O(n)
    right = [x for x in arr[1:] if x >= pivot]   # O(n)
    
    # Худший случай: O(n²)
    # Средний случай: O(n log n) — разделяем пополам
    return quick_sort(left) + [pivot] + quick_sort(right)
# Сложность: O(n log n) в среднем, O(n²) в худшем

Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # Рекурсия: log n уровней
    right = merge_sort(arr[mid:])     # Рекурсия: log n уровней
    
    return merge(left, right)         # Слияние: O(n) на каждом уровне
    # Итого: log n уровней * O(n) = O(n log n)

4. Big Omega (Ω) — нижняя граница

Показывает минимальное время выполнения в лучшем случае.

def search(arr, target):
    for x in arr:
        if x == target:
            return True  # Лучший случай: O(1) — Ω(1)
    return False
# Худший случай: O(n)
# Лучший случай: Ω(1)

5. Big Theta (Θ) — точная граница

Показывает, когда Big O = Big Omega.

# Для простых алгоритмов часто Θ = O = Ω
def sum_array(arr):
    total = 0
    for x in arr:  # Всегда n итераций
        total += x
    return total
# O(n) = Ω(n) = Θ(n)

6. Пространственная сложность (Space Complexity)

Оценивает количество памяти для работы алгоритма.

# O(1) — константная память
def count_elements(arr):
    count = 0
    for x in arr:
        count += 1
    return count  # Используем только переменную count

# O(n) — линейная память
def create_copy(arr):
    copy = []
    for x in arr:
        copy.append(x)  # Создаём новый массив размером n
    return copy

# O(log n) — логарифмическая память (рекурсия)
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)
    # Глубина рекурсии: log n → O(log n) памяти для стека

7. Практический анализ (профилирование)

Использование timeit для измерения

import timeit

# O(n)
linear_test = timeit.timeit(
    lambda: linear_search([1,2,3,4,5], 3),
    number=1000000
)
print(f"Linear search: {linear_test}s")

# O(log n)
binary_test = timeit.timeit(
    lambda: binary_search([1,2,3,4,5], 3),
    number=1000000
)
print(f"Binary search: {binary_test}s")

Профилирование с cProfile

import cProfile
import pstats

def slow_function():
    total = 0
    for i in range(1000000):
        total += i
    return total

profiler = cProfile.Profile()
profiler.enable()
slow_function()
profiler.disable()

stats = pstats.Stats(profiler)
stats.sort_stats('cumulative')
stats.print_stats(10)

8. Чек-лист анализа сложности

1. Определи количество циклов (обычно основной фактор)
2. Вложенные циклы перемножаются (O(n) * O(n) = O(n²))
3. Последовательные операции складываются (O(n) + O(n) = O(n))
4. Берём самый медленный шаг (O(n²) + O(n) = O(n²))
5. Отбрасываем константы (O(5n) = O(n))
6. Учитывай память (Space complexity)
7. Рассматривай лучший/худший/средний случаи
8. Профилируй в реальных условиях (теория vs практика)

Выводы

• Big O показывает верхнюю границу (самое важное)
• O(1) < O(log n) < O(n) < O(n log n) < O(n²)
• Вложенные циклы обычно дают O(n²) или хуже
• Рекурсия часто добавляет O(log n) или O(n) к памяти
• Trade-off: память vs время (кэширование, предвычисления)
• Профилируй код для проверки теории