Время выполнения быстрой сортировки

Я пытаюсь освежить свои знания (и, надеюсь, узнать больше) об анализе алгоритмов. Я прошел этот курс два года назад, но сейчас пытаюсь наверстать упущенное.

Я делаю это, выполняя упражнения из классического учебника «Введение в алгоритмы», 2-е издание — CLRS.

Проблема, которую я пытаюсь решить, заключается в следующем:

Упражнение 7.2-2.
Каково время выполнения БЫСТРОЙ СОРТИРОВКИ, когда все элементы массива A имеют одинаковое значение?

Мое решение.
Время работы БЫСТРОЙ СОРТИРОВКИ, когда все элементы массива А имеют одинаковое значение, будет эквивалентно работе БЫСТРОЙ СОРТИРОВКИ в наихудшем случае, поскольку независимо от того, какая опорная точка выбрана, БЫСТРАЯ СОРТИРОВКА должна пройти через все значения в А. И поскольку все значения одинаковы, каждый рекурсивный вызов приведет к несбалансированному разделению.

Таким образом, повторение будет:

Т ( н ) "=" Т ( н − 1 ) + Θ ( н )

Приведенное выше повторение имеет решение (я докажу это позже):

Т ( н ) "=" Θ ( н 2 )

Следовательно, время работы QUICKSORT в этом случае равно

Θ ( н 2 )

Пожалуйста, проверьте, правильно ли я ответил на вопрос :)

Пожалуйста, дайте мне знать, если этот вопрос должен быть размещен в другом месте в сети SE.

Спасибо!

Джейк Клоусон

Это верно.
Возможно, в будущем вы захотите посетить cstheory.stackexchange.com .
@Emre: это не очень хорошее предложение. cstheory.SE предназначен для вопросов исследовательского уровня , а этот определенно не является таковым, поэтому за него проголосовали бы и закрыли. Это не делает его плохим вопросом, конечно, далеко не так!
Более распространено (AFAIK) использование верхнего регистра Θ а не в нижнем регистре θ для обозначения «большой тета».
Задачи 7-1 по CLRS дают инструмент Хоара для быстрой сортировки. Время работы Хора составляет Θ ( н бревно ⁡ н ) когда все элементы имеют одинаковое значение.
Абсолютно хорошо.

Ответы (3)

Ваше решение выглядит полностью правильным.

Ответ зависит от того, как вы выбираете точку опоры. Если вы будете следовать алгоритму, присутствующему в CLSR, который всегда выбирает последний элемент в качестве опорного, это приведет к уравнению Т ( Н ) "=" Т ( Н − 1 ) + Н и поэтому Т ( Н ) "=" О ( Н 2 ) иначе, если вы выберете средний элемент в качестве опорного каждый раз, когда уравнение станет Т ( Н ) "=" 2 Т ( Н / 2 ) + Н что привело бы к Т ( Н ) "=" Θ ( Н бревно ⁡ Н ) .

Способ выбора опорной точки совершенно не имеет значения, так как все значения равны. Только процесс разбиения может гарантировать, что раздел будет сбалансирован. Для этого важно, чтобы сравнения были нестрогими, а не строгими.

Нет, разбиение приведет к идеально сбалансированным подмассивам. Действительно, алгоритм будет искать первый элемент ≥ поворачиваться влево и ≤ поверните направо и поменяйте их местами. Поскольку все элементы равны (и равны опорной точке), крайний левый и крайний правый элемент будут немедленно заменены местами. Это будет продолжаться до тех пор, пока два индекса не встретятся, что произойдет ровно посередине.

Время выполнения быстрой сортировки
СпросиСетьПолитика конфиденциальности1y, 0v