Сортировки, поиск и сложность алгоритмов

Почему один алгоритм за секунду обрабатывает миллион элементов, а другой — мучается на тысяче.

Вычислительная сложность — оценка того, как растёт число операций алгоритма с увеличением размера входных данных.

Зачем это нужно

Сортировка и поиск — самые частые операции в программировании, а понимание сложности отделяет код, который работает «на игрушечных» данных, от кода, который выдержит реальную нагрузку. Эта тема — фундамент алгоритмики, олимпиад и собеседований, а на ЕГЭ она прячется в задачах, где наивное решение «не успевает». Разберём всё на пальцах: без страшных формул, но строго.

Здесь важно понять одну освобождающую мысль: скорость программы определяется в первую очередь не языком и не «мощностью» компьютера, а выбранным алгоритмом. Можно взять самый быстрый язык и новейший процессор, но если алгоритм квадратичный, на миллионе элементов он всё равно будет ползти. И наоборот — правильный алгоритм на скромном устройстве обгонит неправильный на суперкомпьютере. Разница не в проценты, а в тысячи и миллионы раз. Поэтому инженеры оценивают алгоритм ещё до того, как напишут код: они прикидывают, как растёт число операций с размером данных, и отбрасывают заведомо медленные подходы. Это умение — «чувствовать сложность» — отличает того, кто пишет работающий код, от того, кто пишет код, который работает вовремя. Дальше мы выработаем эту интуицию на конкретных примерах поиска и сортировки.

Интуиция сложности: как растёт работа

Представьте, что данных стало в 1000 раз больше. Что будет с временем работы? Для разных алгоритмов ответ разный, и это записывают через «O-большое»:

Разница между O(n) и O(n²) колоссальна: на миллионе элементов линейный алгоритм сделает миллион операций, а квадратичный — триллион. Поэтому выбор алгоритма важнее скорости компьютера.

Линейный поиск: O(n)

Самый простой поиск — пройти по всем элементам и сравнить. Он работает на любых данных, но в худшем случае просматривает всё. Это O(n) — линейная сложность:

def linear_search(data, target):
    for i, x in enumerate(data):
        if x == target:
            return i          # нашли — возвращаем индекс
    return -1                 # не нашли

nums = [4, 8, 15, 16, 23, 42]
print("индекс 16:", linear_search(nums, 16))
print("индекс 99:", linear_search(nums, 99))

Вывод:

индекс 16: 3
индекс 99: -1

Бинарный поиск: O(log n) — но только в отсортированном

Если данные отсортированы, искать можно гораздо умнее. Бинарный поиск каждым шагом смотрит на середину и отбрасывает половину оставшихся элементов. Так в массиве из миллиона элементов нужно всего около 20 шагов вместо миллиона! Это и есть логарифмическая сложность. Реализуем и посчитаем шаги:

def binary_search(data, target):
    lo, hi = 0, len(data) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if data[mid] == target:
            return mid, steps
        elif data[mid] < target:
            lo = mid + 1       # цель правее — отбрасываем левую половину
        else:
            hi = mid - 1       # цель левее
    return -1, steps

data = list(range(1, 1001))    # отсортированный массив 1..1000
idx, steps = binary_search(data, 777)
print(f"число 777 на индексе {idx}, шагов: {steps}")
print("а линейный поиск сделал бы шагов:", 777)

Вывод:

число 777 на индексе 776, шагов: 8
а линейный поиск сделал бы шагов: 777

Восемь шагов против семисот семидесяти семи — вот цена правильного алгоритма. Но помните: бинарный поиск требует отсортированных данных.

Пузырьковая сортировка: понятная, но O(n²)

«Пузырёк» многократно проходит по списку и меняет местами соседей, стоящих не по порядку. Большие элементы постепенно «всплывают» к концу. Алгоритм нагляден, но медленный: два вложенных прохода дают O(n²). Посчитаем число сравнений:

def bubble_sort(a):
    a = a[:]                  # копия, чтобы не портить оригинал
    comparisons = 0
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            comparisons += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]   # обмен
    return a, comparisons

data = [5, 2, 9, 1, 7, 3]
result, comps = bubble_sort(data)
print("отсортировано:", result)
print("сравнений:", comps, " (элементов:", len(data), ")")

Вывод:

отсортировано: [1, 2, 3, 5, 7, 9]
сравнений: 15  (элементов: 6 )

Сортировка выбором: тоже O(n²), но меньше обменов

Другой простой метод: на каждом шаге находим минимум из оставшихся и ставим его на своё место. Сравнений столько же, но обменов всего n−1 — это бывает важно, если обмен «дорогой»:

def selection_sort(a):
    a = a[:]
    for i in range(len(a)):
        min_idx = i
        for j in range(i + 1, len(a)):
            if a[j] < a[min_idx]:
                min_idx = j           # запоминаем индекс минимума
        a[i], a[min_idx] = a[min_idx], a[i]   # ставим минимум на место i
    return a

print(selection_sort([5, 2, 9, 1, 7, 3]))

Вывод:

[1, 2, 3, 5, 7, 9]

А что в реальности? Встроенная сортировка

В реальном коде свою сортировку почти никогда не пишут: встроенная sorted в Python работает за O(n log n) — намного быстрее «пузырька». Но понимать, что внутри, обязательно, иначе вы не оцените, почему она быстрая:

data = [5, 2, 9, 1, 7, 3]
print("по возрастанию:", sorted(data))
print("по убыванию:", sorted(data, reverse=True))

words = ["груша", "яблоко", "ёж", "арбуз"]
print("по длине:", sorted(words, key=len))

Вывод:

по возрастанию: [1, 2, 3, 5, 7, 9]
по убыванию: [9, 7, 5, 3, 2, 1]
по длине: ['ёж', 'груша', 'арбуз', 'яблоко']

Попробуй сам

Сравним рост числа операций для линейного и бинарного поиска на разных размерах — увидите разрыв своими глазами.

import math

print(f"{'n':>10} | {'линейный':>10} | {'бинарный':>10}")
print("-" * 38)
for n in (10, 100, 1000, 1_000_000):
    linear = n                       # худший случай: просмотр всего
    binary = math.ceil(math.log2(n)) # примерно столько делений пополам
    print(f"{n:>10} | {linear:>10} | {binary:>10}")

Вывод:

         n |   линейный |   бинарный
--------------------------------------
        10 |         10 |          4
       100 |        100 |          7
      1000 |       1000 |         10
   1000000 |    1000000 |         20

Частые ошибки

• Применяют бинарный поиск к неотсортированным данным. Он работает только в отсортированном массиве, иначе результат неверен.
• Считают, что O(n²) «нормально». На больших данных квадратичный алгоритм может работать часами там, где линейный справится за секунды.
• Пишут свою сортировку вместо встроенной. В реальном коде sorted почти всегда правильный выбор.
• Портят исходный список при сортировке. list.sort() меняет список на месте; если оригинал нужен, делайте копию или используйте sorted.

Итоги

• Сложность описывает рост числа операций: O(1), O(log n), O(n), O(n²) — и разница огромна.
• Линейный поиск O(n) работает всегда; бинарный O(log n) — быстрее, но требует отсортированных данных.
• Пузырёк и выбор просты, но O(n²); встроенная sorted — O(n log n).
• Правильный алгоритм важнее быстрого компьютера: на миллионе элементов разрыв колоссален.