Czas trwania sortowania za pomocą podprogramu findmax w czarnej ramce

Question

Załóżmy, że masz podprogram z czarną ramką, który może wyodrębnić maksimum z tablicy n elementów w (log n)^a czasie, gdzie 0 <= a <= 1. Próbujesz stworzyć optymalny algorytm sortowania, który korzysta z tego podprogramu.

Oczywistym rozwiązaniem jest wywołanie podprogramu w całej tablicy, zamiana max na ostatni element, a następnie wywołanie iteracyjnie iteracyjnie na A[1, n-1] do A[1, 2].

Czy istnieje lepszy algorytm, który działa szybciej niż czas n*(log n)^a, czy też oczywiste rozwiązanie jest optymalne?

Answer 1

Nie znam dokładnej odpowiedzi, ale oto niektóre wyniki podpowiedź odpowiedź może być naiwny jeden:

Załóżmy dzielimy wejście na 4 części (4 może być podstawiony przez k);

Sortowanie na każdej z 4 części zajmuje n/4 * (log (n/4)^a), łącząc potrzebne wyniki (n/2 + n/2 + n) = 2n;

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

całkowity czas = n (^ A logn) - n/4 * (log4)^a + 2n

Jednakże, jeśli a = 1, rhs = n (log (n)^a); jeśli < 1, rhs> n (log (n)^a).

Tak więc nawet biorąc pod uwagę rzeczywistą perspektywę światową, a nie perspektywę Big-Oh, podejście polegające na podziale może tylko spowolnić je, jeśli < 1 i nie ma żadnych korzyści, gdy a = 1.

Nie wiem, czy są jeszcze inne sztuczki. Mam nadzieję, że to przynajmniej sprowokuje jakieś pomysły!

Answer 2

Nie. W oczekiwaniu potrzebujemy Ω (n log n) bitów z czarnego pola do sortowania n pozycji. Po wywołaniu tablicy o rozmiarze k czarna skrzynka uruchamia dla (log k) ^a kroki i zwraca około bity log k, z prędkością około (log k) ^{1 - a} bitów na krok. Jest to górna granica (log n) ^{1 - a}, więc oczywisty algorytm jest asymptotycznie optymalny.