Шаг 25.
Алгоритмы.
"О-большое" для быстрой сортировки

    На этом шаге рассмотрим "О-большое" для быстрой сортировки.

    Алгоритм быстрой сортировки уникален тем, что его скорость зависит от выбора опорного элемента. Прежде чем рассматривать быструю сортировку, вспомним наиболее типичные варианты времени выполнения для "О-большое".

    На графиках приведены примерные оценки времени при выполнении 10 операций в секунду. Они не претендуют на точность, а всего лишь дают представление о том, насколько различается время выполнения.

    Для каждого времени выполнения также приведен пример алгоритма. Возьмем алгоритм сортировки выбором. Он обладает временем О(n2), и это довольно медленный алгоритм.

    Другой алгоритм сортировки - так называемая сортировка слиянием - работает за время О(n log n). Намного быстрее! С быстрой сортировкой дело обстоит сложнее. В худшем случае быстрая сортировка работает за время О(n2).

    Ничуть не лучше сортировки выбором! Но это худший случай, а в среднем быстрая сортировка выполняется за время О(n log n). Что в данном случае понимается под "худшим" и "средним" случаем? Eсли быстрая сортировка в среднем выполняется за время О(n log n), а сортировка слиянием выполняется за время О(n log n) всегда, то почему бы не использовать сортировку слиянием?

    На следующем шаге рассмотрим определение "худшего" и "среднего" случаев.




Предыдущий шаг Содержание