Что такое асимптотическая оценка сложности алгоритмов

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

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

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

Пример:

# O(n) - линейная сложность
def linear_search(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

# O(n²) - квадратичная сложность
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Big-O оценивает худший случай, игнорируя константы и младшие члены. Например, O(2n + 100) → O(n).