Что такое О большое (Big O notation)

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

Big O описывает худший сценарий. На практике алгоритм с большей сложностью может работать быстрее на малых данных из-за констант (например, O(n) может уступать O(1) только при больших n).

Зачем нужно?

- Сравнение алгоритмов: Позволяет оценить эффективность алгоритмов без привязки к конкретному железу.

- Прогнозирование производительности: Помогает предсказать, как алгоритм будет работать на больших данных.

- Оптимизация кода: Выявление «узких мест» в программе.

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

- O(1) — Постоянная сложность
Время выполнения не зависит от размера данных.
Пример: доступ к элементу массива по индексу.

- O(log n) — Логарифмическая сложность
Время растет логарифмически от размера данных.
Пример: бинарный поиск.

- O(n) — Линейная сложность
Время прямо пропорционально размеру данных.
Пример: поиск в неотсортированном массиве.

- O(n log n) — Линейно-логарифмическая сложность
Характерна для эффективных алгоритмов сортировки.
Пример: быстрая сортировка (quicksort).

- O(n²) — Квадратичная сложность
Время растет пропорционально квадрату размера данных.
Пример: вложенные циклы (пузырьковая сортировка).

- O(2ⁿ) — Экспоненциальная сложность
Время удваивается с каждым新增 элемента.
Пример: рекурсивное вычисление чисел Фибоначчи.

- O(n!) — Факториальная сложность
Худший случай, характерен для задач перебора.
Пример: решение задачи коммивояжера полным перебором.

Как вычисляется?

- Игнорируются константы: O(2n) → O(n), O(500) → O(1).

- Учитывается только старший член: O(n² + n) → O(n²).

Примеры:

# 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²) — квадратичная сложность
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]