Пример (псевдокод): quicksort, который всегда берёт первый элемент как опору — на почти отсортированных данных даёт квадратичное время.
Псевдокод:
partition(A, lo, hi):
pivot = A[lo]
i = lo+1; j = hi
while i <= j:
while i <= hi and A[i] <= pivot: i += 1
while j >= lo+1 and A[j] > pivot: j -= 1
if i < j: swap(A[i], A[j])
swap(A[lo], A[j])
return j
quicksort(A, lo, hi):
if lo < hi:
p = partition(A, lo, hi)
quicksort(A, lo, p-1)
quicksort(A, p+1, hi)
Плохой случай: вход почти отсортирован (или уже отсортирован). Тогда каждый раз опора = первый элемент даёт разбиение $[0,n-1]$ → $[0,n-2]$ + пустое, и рекуррентное соотношение
$$T(n)=T(n-1)+\Theta (n),$$ откуда
$$T(n)=\Theta (n^2).$$
Как эмпирически обнаружить деградацию:
- Профилирование/инструментирование: считать число сравнений и обменов; при плохом выборе опоры число сравнений ~$\Theta (n^2)$ (например, приближённо $n(n-1)/2$).
- Бенчмарки по разным размерам $n$: измерить время $T(n)$ для $n\in \{n_1,n_2,\dots \}$. На лог‑лог графике скорость роста ~$n^2$ даст наклон примерно $2$ (т.е. slope $\approx 2$). Также можно смотреть отношение $T(n)/n^2$ — оно станет примерно постоянным при квадратичном росте.
- Наблюдать глубину рекурсии: при плохой опоре глубина ≈ $n$ вместо $O(\log n)$.
- Тестировать на особых входах: уже отсортированные, обратно отсортированные, почти одинаковые ключи — если время резко возрастает, есть проблема с опорой.
Стратегии улучшения и оценка эффектов:
1) Рандомизация (выбирать случайную опору):
- Эффект: среднее время $\Theta (n\log n)$ с высокй вероятностью; для случайной опоры вероятность худшего случая экспоненциально мала.
- Минусы: теоретически худший случай остаётся $\Theta (n^2)$, небольшой дополнительный overhead на генерацию случайного числа.
- Рекомендация: простое и эффективно против адаптивных/вредоносных входов.
2) Медиана из трёх (median-of-three: первый, середина, последний):
- Эффект: на уже/почти отсортированных данных часто даёт хорошую опору (средний элемент), приближая баланс разбиений → практическое $\Theta (n\log n)$.
- Минусы: небольшое дополнительное число сравнений при выборе опоры; не защищает от всех худших случаев, но устраняет типичные паттерны (sorted, reverse).
- Часто эффективна как low-cost heuristic.
3) Переключение на вставками для малых подмассивов:
- Метод: если размер подмассива $\le k$ (обычно $k\in [10,50]$), использовать insertion sort.
- Эффект: insertion sort имеет $\Theta (k^2)$ на подмассиве, но низкие константы; уменьшает общие накладные расходы и ускоряет практическое выполнение.
- Минусы: нужно подобрать порог $k$ эмпирически.
4) Introsort (hybrid): начинать как quicksort, при глубине рекурсии > $c\log n$ переключиться на heapsort.
- Эффект: гарантирует худшее время $\Theta (n\log n)$ и при этом сохраняет быструю среднюю производительность quicksort.
- Минусы: более сложная реализация; переключение увеличивает константы.
5) Трёхпутевое разбиение (Dutch national flag) для большого числа равных ключей:
- Эффект: при многих одинаковых ключах время становится $\Theta (n)$ (или близко), избегая деградации, вызванной равными элементами.
- Минусы: логика сложнее; лучше для данных с множеством дубликатов.
Рекомендация на практике:
- Комбинация: выбирать опору как случайную или median-of-three; использовать трипартитное разбиение, порог на insertion sort ($k\approx 16$–$32$); для гарантии худшего случая — introsort. Это даёт быстрый средний случай и защищённость от квадратичной деградации.
Краткое резюме (эффекты на плохом входе "почти отсортирован"):
- простой выбор первого элемента → $\Theta (n^2)$;
- рандомизация или median-of-three → ожидаемо $\Theta (n\log n)$ на таких входах;
- cutoff→insertion уменьшает константы, ускоряя практическое выполнение;
- introsort даёт гарантию $\Theta (n\log n)$ в худшем случае.