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

Big O нотация и вычислительная сложность алгоритмов

Big O (О большое) — это математическое обозначение, которое описывает, как алгоритм масштабируется с ростом размера входных данных. Это критически важно для оптимизации и выбора правильного алгоритма.

Основная идея Big O

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

# O(1) — константное время
def get_first_element(arr):
    return arr[0]  # 1 операция, всегда

# 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²) — квадратичное время
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):          # n итераций
        for j in range(n - 1):  # еще n итераций
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Основные классы сложности (от лучшей к худшей)

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

Операция всегда выполняется за одно и то же время, независимо от размера входа.

def get_value_by_key(dictionary, key):
    return dictionary[key]  # Хеш-таблица: O(1) в среднем

def is_first(arr):
    return arr[0] == 5  # Индексный доступ: 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

# Каждая итерация сокращает размер в 2 раза
# Для массива из 1 млн элементов: log(1000000) ≈ 20 итераций

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

Операция зависит от размера входа линейно.

def sum_elements(arr):
    total = 0
    for num in arr:  # n операций
        total += num
    return total

def contains(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

O(n log n) — Линейно-логарифмическая

Типично для хороших алгоритмов сортировки (merge sort, quick sort).

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

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

Вложенные циклы. Часто плохо для больших входов.

# Bubble sort, Selection sort
def selection_sort(arr):
    for i in range(len(arr)):       # n итераций
        for j in range(i+1, len(arr)):  # n итераций
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]
    return arr

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

Очень плохо. Удваивается с каждым увеличением входа.

# Наивный fibonacci — O(2^n)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)  # Экспоненциальное ветвление

# fib(40) потребует миллиарды операций!

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

Самая плохая.

# Перебор всех перестановок
def generate_permutations(arr):
    if len(arr) == 1:
        return [arr]
    perms = []
    for i, item in enumerate(arr):
        for perm in generate_permutations(arr[:i] + arr[i+1:]):
            perms.append([item] + perm)
    return perms

Порядок от лучшего к худшему

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)

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

Для n = 1000:
O(1)        → 1 операция
O(log n)    → 10 операций
O(n)        → 1000 операций
O(n log n)  → 10000 операций
O(n²)       → 1000000 операций
O(2^n)      → 10^301 операций (НЕВОЗМОЖНО!)

Практические примеры оптимизации

# ПЛОХО: O(n²)
def has_duplicates_slow(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# ХОРОШО: O(n)
def has_duplicates_fast(arr):
    seen = set()
    for num in arr:
        if num in seen:  # O(1) поиск в set
            return True
        seen.add(num)
    return False

# Для массива из 10000 элементов:
# Slow: 100 млн операций
# Fast: 10000 операций

Сложность методов Python

# Список
list[i]              # O(1) — доступ по индексу
list.append(x)       # O(1) амортизированный
list.insert(i, x)    # O(n) — сдвиг элементов
list.remove(x)       # O(n) — поиск и удаление
list.sort()          # O(n log n) — тим-сорт

# Словарь
dict[key]            # O(1) в среднем
dict[key] = val      # O(1) в среднем
key in dict          # O(1) в среднем

# Set
elem in set          # O(1) в среднем
set.add(elem)        # O(1) в среднем

# Строка
str[i]               # O(1)
str.find(substr)     # O(n*m) где m — длина подстроки

Как анализировать сложность?

def analyze_complexity(arr):
    # O(1) — присваивание
    x = 5
    
    # O(n) — один цикл
    for item in arr:
        x += item
    
    # O(n) — еще один цикл (не O(n²)!)
    for item in arr:
        print(item)
    
    # Итого: O(n) + O(n) = O(n) — берем доминирующий член

def nested_complexity(arr):
    # O(n²) — вложенные циклы
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[i] == arr[j]:
                pass

Вывод

Big O нотация — это инструмент для:

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

При интервью часто спрашивают о временной и пространственной сложности алгоритмов — нужно уметь быстро анализировать код и называть сложность.