От чего зависит скорость выполнения алгоритма в нотации Big O?

# Big O Notation: от чего зависит скорость выполнения алгоритма

Big O notation описывает, как растёт время выполнения (или потребление памяти) алгоритма в зависимости от размера входных данных. Это асимптотический анализ сложности.

Ключевая суть: зависимость от размера входа

Скорость выполнения в Big O зависит исключительно от размера входных данных (n). Вот что НЕ влияет:

• Конкретные значения данных
• Константные множители
• Машина, на которой выполняется
• Язык программирования

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

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

Время выполнения не зависит от размера входа:

def get_first_element(lst):
    return lst[0]  # Всегда O(1), независимо от длины списка

def add_two_numbers(a, b):
    return a + b   # O(1) — операция выполняется за фиксированное время

# Доступ к элементу по индексу в списке
arrays = [10, 20, 30, 40, 50]
print(arrays[2])  # 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  # Отбрасываем половину
    
    return -1  # O(log n) — каждая итерация уменьшает поиск вдвое

Для массива из 1 000 000 элементов потребуется максимум ~20 сравнений.

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

Время растёт линейно с размером входа. Нужно обойти каждый элемент один раз:

def find_max(arr):
    max_val = arr[0]
    for num in arr:  # Проходим все n элементов
        if num > max_val:
            max_val = num
    return max_val  # O(n)

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

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:])     # Разбиваем (log n слоёв)
    
    return merge(left, right)  # Слияние O(n) на каждом слое
                               # Итого: O(n log n)

# Встроенная сортировка Python
sorted(arr)  # O(n log n) — Timsort

O(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²)

def check_all_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[i] == arr[j]:  # Проверяем все n² пар
                pass

O(n³) — Кубическая сложность

Три вложенных цикла:

def matrix_multiplication(A, B, size):
    result = [[0] * size for _ in range(size)]
    
    for i in range(size):          # Цикл 1: n итераций
        for j in range(size):      # Цикл 2: n итераций
            for k in range(size):  # Цикл 3: n итераций
                result[i][j] += A[i][k] * B[k][j]
    
    return result  # O(n³)

O(2^n) — Экспоненциальная сложность

Время экспоненциально растёт. Часто встречается в рекурсивных алгоритмах без оптимизации:

def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)  # O(2^n)

# Для n=50 это выполняется примерно 10^15 операций!

O(n!) — Факториальная сложность

Крайне медленная сложность. Встречается в переборе всех перестановок:

def generate_permutations(arr):
    if len(arr) <= 1:
        return [arr]
    
    perms = []
    for i, num in enumerate(arr):
        remaining = arr[:i] + arr[i+1:]
        for perm in generate_permutations(remaining):
            perms.append([num] + perm)
    
    return perms  # O(n!) — число перестановок = n!

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

Время выполнения при n=100:

O(1)        — 1 операция
O(log n)    — ~7 операций
O(n)        — 100 операций
O(n log n)  — ~700 операций
O(n²)       — 10,000 операций
O(n³)       — 1,000,000 операций
O(2^n)      — 10^30 операций (НЕВОЗМОЖНО!)
O(n!)       — 9.3 * 10^157 операций (НЕВОЗМОЖНО!)

От чего конкретно зависит Big O

1. Количество циклов

# O(n) — один цикл
for i in range(n):
    print(i)

# O(n²) — два вложенных цикла
for i in range(n):
    for j in range(n):
        print(i, j)

# O(n³) — три вложенных цикла
for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i, j, k)

2. Рекурсивные вызовы

# O(2^n) — каждый вызов порождает 2 новых
def recursive(n):
    if n <= 0:
        return 1
    return recursive(n-1) + recursive(n-1)

# O(n) — каждый вызов порождает 1 новый
def linear_recursive(n):
    if n <= 0:
        return 1
    return linear_recursive(n-1)

3. Деление пополам (бинарный поиск)

# O(log n) — каждую итерацию делим на 2
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

Важные уточнения

Лучший, средний и худший случаи

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Лучший случай O(1): элемент в начале
# Средний случай O(n): в среднем элемент в середине
# Худший случай O(n): элемента нет или он в конце

Игнорирование констант

# O(2n) = O(n)  — константные множители игнорируются
for i in range(n):
    process1(i)
for i in range(n):
    process2(i)

# O(n + 100) = O(n)  — константы игнорируются
for i in range(n):
    print(i)
for i in range(100):
    print("fixed")

Доминирующий член

# O(n² + n + 1) = O(n²)  — доминирует n²
for i in range(n):
    for j in range(n):        # n²
        print(i, j)
for i in range(n):            # n
    print(i)
print("done")                # 1

Практическая таблица временной сложности алгоритмов

Заключение

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

• Выбора правильного алгоритма
• Оптимизации кода
• Прогнозирования производительности при больших данных
• Проведения code review и архитектурных решений