Время выполнения сортировки с подпрограммой findmax черного ящика

Question

Предположим, у вас есть подпрограмма черного ящика, которая может извлечь максимум из массива из n элементов за (log n)^a время, где 0 <= a <= 1. Вы пытаетесь создать оптимальный алгоритм сортировки, который использует эту подпрограмму.

Очевидное решение состоит в том, чтобы вызвать подпрограмму для всего массива, поменять макс с последним элементом, а затем вызвать подпрограмму итеративно с A[1, n-1] до A[1, 2].

Есть ли лучший алгоритм, который работает быстрее, чем n*(log n)^a время, или очевидное решение оптимально?

Answer 1

Нет. В ожидании нам понадобится Ω (n log n) битов из черного ящика для сортировки n элементов. При вызове массива размером k черный ящик запускается для (log k) ^a шагов и возвращает около log k битов со скоростью около (log k) ^{1 - a} бит на шаг. Эта скорость ограничена сверху (log n) ^{1 - a} , поэтому очевидный алгоритм асимптотически оптимален.

Answer 2

Я не знаю точного ответа, но вот некоторые результаты, намекающие на то, что ответ может быть наивным:

Предположим, мы разделим входные данные на 4 части (4 можно заменить на k);

Сортировка по каждому из 4 фрагментов занимает n / 4 * (log (n / 4) ^ a), объединяя необходимые результаты (n / 2 + n / 2 + n) = 2n;

n / 4 * (log (n / 4) ^ a) * 4 = n (logn ^ a) -n / 4 * (log4) ^ a,

общее время = n (logn ^ a) - n / 4 * (log4) ^ a + 2n

Однако, если a = 1, rhs = n (log (n) ^ a);если a <1, rhs> n (log (n) ^ a).

Таким образом, даже с точки зрения реального мира, а не перспективы Big-Oh, подход «разделяй и властвуй» может замедлить его, только еслиa <1, и если a = 1. </p>

никаких преимуществ нет, однако я не знаю, есть ли другие хитрости.Надеюсь, что это может хотя бы спровоцировать некоторые идеи!