Что такое асимптотическая оценка сложности алгоритмов?

Асимптотическая оценка сложности алгоритмов (Big-O, Big-Theta, Big-Omega)

Асимптотическая оценка — это математический способ анализа эффективности алгоритмов без привязки к конкретному компьютеру или языку. Показывает, как меняется время выполнения и использование памяти при увеличении размера входных данных.

Нотации сложности

O-большое (Big-O) — верхняя граница, worst-case

# O(1) — константная сложность
def get_first_element(arr):
    return arr[0]

# O(n) — линейная сложность
def find_max(arr):
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

# O(n^2) — квадратичная сложность
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# 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
    return -1

# O(n log n) — лучшие сортировки
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Omega-большое (Big-Ω) — нижняя граница, best-case:

• Линейный поиск: Ω(1) если элемент в начале

Theta-большое (Big-Θ) — точная граница, average-case:

• Merge sort: Θ(n log n) всегда

Иерархия сложностей (от лучшей к худшей)

1. O(1) — константная (очень быстро)
2. O(log n) — логарифмическая (двоичный поиск)
3. O(n) — линейная (простые циклы)
4. O(n log n) — линейно-логарифмическая (эффективные сортировки)
5. O(n²) — квадратичная (вложенные циклы)
6. O(n³) — кубическая (три вложенных цикла)
7. O(2^n) — экспоненциальная (рекурсия без оптимизации)
8. O(n!) — факториальная (очень медленно)

Практический пример для Data Engineer

Выбор между подходами при обработке 1 миллиона записей:

import time

# O(n) решение
def count_duplicates_dict(items):
    """Один проход по данным, O(n)"""
    counts = {}
    for item in items:
        counts[item] = counts.get(item, 0) + 1
    return counts

# O(n²) решение — НЕ используй!
def count_duplicates_nested(items):
    """Два вложенных цикла, O(n²)"""
    counts = {}
    for item in items:
        count = 0
        for other in items:
            if item == other:
                count += 1
        counts[item] = count
    return counts

# На 1М элементов:
# O(n) — ~0.1 сек
# O(n²) — ~100,000 сек = 27 часов!

Сложность памяти (Space Complexity)

# O(1) — константная память
def sum_array(arr):
    total = 0  # одна переменная
    for num in arr:
        total += num
    return total

# O(n) — линейная память
def create_copy(arr):
    return arr.copy()  # копия всего массива

# O(n²) — квадратичная память
def create_matrix(n):
    return [[0 for _ in range(n)] for _ in range(n)]  # матрица n×n

Правила вычисления сложности

1. Константы отбрасываются: O(2n) = O(n)
2. Младшие степени отбрасываются: O(n² + n) = O(n²)
3. Последовательные операции складываются: O(n) + O(n) = O(n)
4. Вложенные циклы перемножаются: O(n) * O(n) = O(n²)

Анализ примера с SQL запросом

-- O(log n) — индексированная колонка, бинарный поиск
SELECT * FROM users WHERE id = 123;

-- O(n) — полный скан таблицы
SELECT * FROM users WHERE email LIKE '%@gmail.com';

-- O(n log n) — сортировка в памяти
SELECT * FROM users ORDER BY created_at;

-- O(n * m) — декартово произведение двух таблиц
SELECT * FROM users JOIN orders ON users.id = orders.user_id;

Когда асимптотика критична

Для Data Engineer важно на этапе проектирования:

• Выбор структур данных — Dict vs List для поиска
• Выбор алгоритма сортировки — при 1М+ записей
• SQL оптимизация — индексы vs полный скан
• Параллелизм — Spark при O(n²) операциях

Осложность O(n) с 1М элементов vs O(n²) — это разница между 1 секундой и часами обработки данных.