Какова временная сложность алгоритма в лучшем и худшем случаях?

Временна́я сложность алгоритма — это функция, описывающая зависимость количества выполняемых элементарных операций от размера входных данных. Говоря про лучший и худший случаи, мы рассматриваем минимально и максимально возможное время работы для данного размера набора данных. Чаще всего нас интересует именно худший случай — он даёт гарантию, что алгоритм не будет работать дольше указанной оценки.

Лучший случай — это ситуация, когда входные данные приводят к минимальному числу операций. Например, для сортировки пузырьком (bubble sort) лучший случай — уже отсортированный массив. В этом случае алгоритм просто проходит по массиву один раз, не выполняя перестановок, и его временная сложность — O(n).

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

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

Пример на Python для линейного поиска:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Лучший случай: элемент найден на первой позиции — O(1). Худший случай: элемент в конце или отсутствует — O(n).

Для практического собеседования стоит помнить:

• Лучший случай часто бесполезен для оценки выбора алгоритма, если только не гарантируется специальный характер данных (например, почти отсортированный массив для timsort).
• Худший случай — основная метрика, так как даёт верхнюю границу.
• Иногда важна и средняя сложность (например, у быстрой сортировки худший O(n²), но средний O(n log n)).