Rozwiązywanie relacji cykliczności za pomocą dwóch wywołań rekurencyjnych

Studiuję najgorszy czas wykonywania Quicksort pod warunkiem, że nigdy nie zrobi bardzo niezrównoważonej partycji dla różnych definicji bardzo .

Aby to zrobić, zadaję sobie pytanie, jaki byłby czas działania w przypadku, gdy Quicksort zawsze zdarza się podzielić na ułamek taki, że Elementy znajdują się w lewej przegrodzie, a znajdują się w prawej przegrodzie (pozostawiając element, oś obrotu, pośrodku).$T(n, p)$$0 < p \leq {1\over 2}$$\lfloor{p(n-1)}\rfloor$$\lceil(1 - p)(n - 1)\rceil$$1$

Nie powinno być trudno zauważyć, że daje górną granicę w najgorszym przypadku, gdy jest maksymalnie niezrównoważoną dozwoloną partycją, ponieważ każda partycja z ułamkiem będzie bardziej zrównoważona i będzie miała krótszy czas działania, oraz jakakolwiek frakcja jest niedozwolona.$T(n, p)$$p$$> p$$<p$

Oczywiste jest, że jest najlepszym przypadkiem, a jest najgorszym przypadkiem szybkiego sortowania. Oba mają łatwe relacje nawrotów, które można znaleźć w dowolnym zasobie edukacyjnym. Ale nie mam pojęcia, jak badać w ogóle. Oczywista relacja wyglądałaby następująco:$T(n, {1 \over 2})$$T(n, 0)$$T(n, p)$

Utknąłem. Próbowałem szukać, ale cała literatura, którą mogłem zrozumieć na temat algorytmów dzielenia i zdobywania, zawierała „podział” dosłownie i „oszukiwała” analizę, wykorzystując fakt, że partycje są zawsze równej wielkości, łącząc terminy w jeden raz stały.

Nie wiem, jak poradzić sobie z dwoma połączeniami rekurencyjnymi i nie wiem, czy usunięcie zaokrąglenia jest bezpieczne. Czy można to rozwiązać analitycznie, a jeśli tak, to w jaki sposób?

PS: Nie interesują mnie asymptotyki (które można łatwo pokazać dla dowolnej stałej ). Interesuje mnie, o ile wolniejsze jest szybkie sortowanie, gdy maleje, na przykład interesuje mnie stosunek .$\Theta(n \log n)$$p$$p$$T(n, 0.25) \over T(n, 0.5)$

PPS: Jako student studiów przepraszam, że uczyniłem oczywiste rzeczy zbyt długimi lub niewyjaśnionymi nietrywialnościami. I choć nie wiem, czy jest to tak bardzo zaniedbywane, jak inne witryny SE, zauważę, że jest to osobisty interes, a nie praca domowa.

Jak wspomniałeś, twierdzenie Akra – Bazzi pokazuje, że rozwiązaniem rekurencji jest dla wszystkich . Nie ujawnia to jednak charakteru zależności od . Aby ustalić to drugie, możemy zastosować podejście drzewa rekurencyjnego.$T(n,p)$$O(n\log n)$$p \in (0,1)$$p$

W katalogu głównym drzewa rekurencji jest interwał . Jego dwoje potomków to przedziały i , których łączna długość wynosi ponownie . Każdy z tych węzłów ma dwoje dzieci (zakładając, że jest wystarczająco duży) i tak dalej. Dla uproszczenia ignorujemy błędy zaokrąglania, tzn. Zakładamy, że jest liczbą całkowitą; to tylko technika i nie martwiłbym się tym. Zatrzymujemy proces za każdym razem, gdy węzeł ma długość co najwyżej . Złożoność algorytmu jest proporcjonalna do całkowitej długości interwałów w drzewie. Kiedy , liście$\{1,\ldots n\}$$\{1,\ldots,pn\}$$\{pn+1,\ldots,n\}$$n$$n$$pn$$1$$p \neq 1/2$ (węzły, na których zatrzymujemy proces) mają różną głębokość, co utrudnia określenie ogólnej złożoności.

Możemy uzyskać prostą górną granicę, zauważając, że drzewo ma co najwyżej poziomy: każdy węzeł jest co najmniej mniejszy niż jego rodzic. Podobnie jak w analizie dla , całkowita długość przedziałów na dowolnym poziomie wynosi co najwyżej , i otrzymujemy górną granicę na czas trwania. Ponieważ i dla małego , możemy to zapisać jako .$\log_{1-p} (1/n)$$1-p$$p = 1/2$$n$$O(n\log_{1-p} (1/n))$$\log_{1-p} (1/n) = \log n/\log (1-p)^{-1}$$\log (1-p)^{-1} = -\log (1-p) = p \pm O(p^2)$$p$$O(n\log n/p)$

Oto dokładniejsze obliczenia. Rozważ poziom . Załóżmy, że nie zatrzymamy procesu po osiągnięciu krótkiego odstępu czasu. Możemy wygenerować losowy wierzchołek, wykonując kroków, w każdym z których idziemy w lewo (powiedzmy) z prawdopodobieństwem i w prawo (powiedzmy) z prawdopodobieństwem . Za każdym razem, gdy wykonujemy lewy krok, dziennik długości interwału zmniejsza się o , a za każdym razem, gdy robimy prawy krok, zmniejsza się o . Wierzchołek znajduje się w rzeczywistym drzewie dziennika o długości zmniejszonej maksymalnie o . Łączna waga interwałów na poziomie$t$$t$$p$$1-p$$-\log p$$-\log (1-p)$$\log n$$t$drzewa jest dokładnie prawdopodobieństwem, że wierzchołek wygenerowany zgodnie z tym procesem odpowiada co najwyżej zmniejszeniu . Oznacza to, że jeśli jest rozkładem równym z prawdopodobieństwem oraz z prawdopodobieństwem , a są niezależne, to całkowita waga poziomu wynosi . Dla superstałej zmienna losowa jest z grubsza normalnie rozkładana ze średnią wariancją liniową$\log n$$D$$-\log p$$p$$-\log(1-p)$$1-p$$X_1,\ldots,X_t \sim D$$t$$\Pr[X_1+\cdots+X_t \leq \log n]$$t$$X_1+\cdots+X_t$$[-p\log p-(1-p)\log(1-p)]t$$t$, więc dla spełniającego , powiedzmy, prawdopodobieństwo będzie bardzo bliskie , podczas gdy dla spełnianie , powiedzmy, będzie bardzo bliskie zeru. Definiując (znany jako binarna funkcja entropii), dochodzimy do wniosku, że czas działania to (jednolite w , jak ). Jako mamy , więc nasze wcześniejsze oszacowanie nie było ścisłe.$t$$[-p\log p-(1-p)\log(1-p)]t \leq (\log n)/2$$1$$t$$[-p\log p-(1-p)\log(1-p)]t \geq 2\log n$$h(p) = -p\log p-(1-p)\log(1-p)$$\Theta(n\log n/h(p))$$p$$n\to\infty$$p\to 0$$h(p) \approx -p\log p$

Innym sposobem spojrzenia na tę samą analizę jest posiadanie nieskończonej sekwencji niezależnych zmiennych losowych jak poprzednio i zdefiniowanie czasu zatrzymania jako pierwszego tak aby . Czas działania jest wówczas proporcjonalny do . Twierdzenie o elementarnym odnowieniu stwierdza następnie, że , co oznacza, że całkowity rozmiar przedziałów wynosi . Dokładniej, dla każdej stałej całkowity rozmiar przedziałów wynosi , gdzie$X_1,X_2,\ldots$$T$$t$$X_1 + \cdots + X_t \geq \log n$$n\mathbb{E}[T]$$\lim_{n\to\infty} \mathbb{E}[T]/\log n = 1/\mathbb{E}[D] = 1/h(p)$$(1+o(1))n\log n/h(p)$$p$$(1+\alpha_p(n))n\log n/h(p)$$\alpha_p(n) = o(n)$ . Konwergencja w elementarnym twierdzeniu o odnowieniu jest wykładnicza w parametrze czasu - w naszym przypadku - więc powinna być wielomianowa w , to znaczy . Prawdopodobnie zbieżność jest również jednolita dla dla dowolnego .$\log n$$n$$\alpha_p(n) = O(n^{-C_p})$$p \in (\delta,1-\delta)$$\delta > 0$

Podsumowując, całkowita długość przedziałów w drzewie rekurencyjnym, która jest proporcjonalna do czasu działania, ma następującą postać dla każdego : gdzie i są przenoszone do tej samej bazy, a jest funkcją zależną od i zmierzającą do pomocą .$p$

Co więcej, prawdopodobnie prawdą jest, że dla dowolnego i dowolnego prawdą jest, że całkowita długość przedziałów ma postać gdzie i ukryta duża stała O zależą tylko od . W szczególności powinno być tak, że dla wszystkich stałych , a konwergencja jest wielomianowo szybka.$\delta > 0$$p \in (\delta,1-\delta)$