Что такое оценка сложности алгоритма

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

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

• O(1) — константная (доступ к элементу массива)
• O(log n) — логарифмическая (бинарный поиск)
• O(n) — линейная (поиск в неотсортированном массиве)
• O(n log n) — линейно-логарифмическая (быстрая сортировка)
• O(n²) — квадратичная (пузырьковая сортировка)

Пример:

# 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

Big-O оценивает худший случай, но бывают и другие оценки (Ω — лучший, Θ — средний).