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

Алгоритмическая сложность (Big O Notation)

Алгоритмическая сложность — это способ анализа эффективности алгоритма в зависимости от объёма входных данных. Она описывает, как растёт время выполнения или потребление памяти при увеличении размера входных данных (обозначается как n).

Нотация Big O

Big O (big-oh) — это верхняя граница роста функции. Она показывает худший случай сложности алгоритма.

Основные виды сложности

Примеры анализа

O(1) - Константная сложность

def get_first_element(arr):
    return arr[0]  # Всегда один доступ, независимо от размера arr

O(n) - Линейная сложность

def find_max(arr):
    max_value = arr[0]
    for i in range(len(arr)):  # Один цикл по n элементам
        if arr[i] > max_value:
            max_value = arr[i]
    return max_value

O(n²) - Квадратичная сложность

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]  # Обмен
    return arr

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])  # Рекурсия: log n уровней
    right = merge_sort(arr[mid:])  # Каждый уровень обрабатывает n элементов
    
    return merge(left, right)  # Слияние: O(n)

Важные правила анализа

1. Константы игнорируются

# O(2n) упрощается до O(n)
# O(10n) упрощается до O(n)
# O(n/2) упрощается до O(n)

2. Берётся старший член

# O(n² + n + 1) упрощается до O(n²)
# O(n³ + 2n²) упрощается до O(n³)
for i in range(n):      # O(n)
    for j in range(n):  # O(n²) - этот доминирует
        pass

3. Разные переменные

# Если два независимых цикла
for i in range(n):      # O(n)
    pass
for j in range(m):      # O(m)
    pass
# Итого: O(n + m)

# Если вложенные циклы
for i in range(n):      # O(n * m)
    for j in range(m):
        pass
# Итого: O(n * m)

Практическое применение в Data Engineering

При обработке данных в Spark или Hadoop:

Скорость обработки:

• 1 млн записей с O(n): ~1 сек
• 1 млн записей с O(n log n): ~20 сек
• 1 млн записей с O(n²): недели

Для Data Engineer важно:

1. Писать эффективные SQL-запросы и трансформации
2. Выбирать правильные алгоритмы сортировки, поиска
3. Оптимизировать JOIN операции (O(n) вместо O(n²))
4. Использовать индексы для быстрого поиска O(log n) вместо O(n)

Другие типы анализа

• Лучший случай (Big Omega, Ω) — минимальное количество операций
• Средний случай (Theta, Θ) — среднее распределение
• Пространственная сложность — требуемая память, анализируется аналогично

Понимание алгоритмической сложности критично для создания масштабируемых систем обработки данных.