Вопросы с тегом «quicksort»

18
Почему рандомизированная быстрая сортировка имеет O (n log n) наихудших затрат времени выполнения

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

16
Почему бы нам не использовать быструю сортировку в связанном списке?

Алгоритм быстрой сортировки можно разделить на следующие шаги Определить опору. Разделите связанный список на основе сводки. Разделите связанный список рекурсивно на 2 части. Теперь, если я всегда выбираю последний элемент как сводный, то для идентификации сводного элемента (1-й шаг) требуется...

14
Требуется ли транзитивность для алгоритма сортировки

Можно ли использовать алгоритм сортировки с нетранзитивным сравнением, и если да, почему транзитивность указана в качестве требования для сортировки компараторов? Фон: Алгоритм сортировки обычно сортирует элементы списка в соответствии с функцией сравнения C (x, y), с...

11
Нахождение k-го наименьшего элемента из заданной последовательности только с O (k) памятью O (n) времени

Предположим , что мы читаем последовательность чисел, один за другим. Как найти к «й наименьший элемент только с помощью O ( K ) клеток памяти и в линейном времени ( O ( п ) ). Я думаю , что мы должны сохранить первые K члены последовательности и когда получим K + 1 «й член, удалить термин ,...

10
Пытаясь понять это быстрое доказательство правильности

Это доказательство является доказательством по индукции и состоит в следующем: P (n) - это утверждение, что «Быстрая сортировка правильно сортирует каждый входной массив длины n». Базовый случай: каждый входной массив длины 1 уже отсортирован (P (1) выполняется) Шаг индукции: fix n => 2....