Каковы будут отношения повторения для этого алгоритма?

Question

Мне был дан этот алгоритм, который вычисляет медиану массива и разделяет остальные элементы вокруг него.

Он помещает все элементы, меньшие, чем медиана в наборе A1, все равные ему в A2 и все те, которые больше в A3. Если A1 больше 1, он рекурсивно входит в него, и то же самое происходит для A3. Он заканчивается после копирования конкатенации A1, A2 и A3 в A.

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

Что я знаю, так это то, что в быстрой сортировке сложность времени равна T (n) = n -1 + T (a) + T (n -a-1), где n - 1 для раздела, T (a) рекурсивный вызов в первой части, а t (na-1) рекурсивный вызов в последней части. В этом случае худший сценарий произошел, когда ось всегда была самым большим или самым маленьким элементом в массиве.

Но теперь, поскольку у нас медиана в качестве оси, каким может быть наихудший случай?

Answer 1

Вы можете использовать алгоритм Big 5, который даст вам приблизительную медиану. Если вы используете это как свою точку в быстрой сортировке, сложность в худшем случае будет O (n log n) вместо O (n ^ 2), так как мы делаем равные деления каждый раз вместо худшего случая, когда мы делим неравномерно с одно ведро с одним элементом, а другое с n - 1 элементами.

С другой стороны, этот худший случай маловероятен. При поиске точки поворота с использованием алгоритма медианы Big 5 прилично накладные расходы связаны с тем, что на практике она превосходит выбор случайных осей. Но если вы хотите найти медиану каждый раз, наихудший случай будет O (n logn)