Что такое сложность алгоритмов Big O (O(1), O(n), O(n²))? Объясните, как работает сортировка пузырьком и почему её сложность O(n²)?

Короткий ответ

Big O описывает, как растёт время выполнения или потребление памяти алгоритма при увеличении размера входных данных n: O(1) — константно, O(n) — линейно, O(n²) — квадратично. Сортировка пузырьком сравнивает соседние элементы и меняет их местами при нарушении порядка, поэтому из-за вложенных циклов в худшем случае работает за O(n²).

Как это работает подробнее

О-нотация оценивает асимптотику и худший случай, а не точное время. Пузырёк устроен просто: после каждого полного прохода наибольший элемент «всплывает» в конец неотсортированной части.

• Смысл нотации. О-нотация задаёт верхнюю границу роста в худшем случае; константы и младшие слагаемые отбрасывают, поэтому 3n² + 2n + 1000 — это O(n²).
• Константная сложность. O(1) — время не зависит от размера входа: обращение к элементу по индексу или проверка вхождения в set.
• Линейная сложность. O(n) — время растёт пропорционально n, как при суммировании всех элементов списка одним циклом.
• Квадратичная сложность. O(n²) появляется при вложенных циклах по одним и тем же данным, когда число операций порядка n².
• Сложность пузырька. Внешний цикл делает до n проходов, внутренний — до n сравнений, итого около n²/2 сравнений в худшем случае, отсюда O(n²); флаг swapped даёт досрочный выход за O(n) на отсортированном списке.

Пример кода

Сортировка пузырьком с ранним выходомКопировать

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr)  # [11, 12, 22, 25, 34, 64, 90]