Lösen der Wiederholungsbeziehung mit zwei rekursiven Aufrufen

10

Ich untersuche die Worst-Case-Laufzeit von Quicksort unter der Bedingung, dass niemals eine sehr unausgeglichene Partition für unterschiedliche Definitionen von sehr ausgeführt wird .

Dazu stelle ich mir die Frage, wie die Laufzeit T(n,p) aussehen würde, wenn Quicksort immer in einem Bruchteil 0 < p 1 partitioniert0<p12 so dass sichp(n1)Elemente in der linken Partition und(1p)(n1)in der rechten Partition befinden (wobei1Element, der Drehpunkt, in der Mitteverbleibt).

Es sollte nicht schwer zu erkennen sein, dass T(n,p) eine Obergrenze für den schlimmsten Fall ergibt, in dem p die maximal unsymmetrische zulässige Partition ist, da jede Partition mit Bruch >p ausgeglichener ist und eine kleinere Laufzeit hat, und Ein Bruch <p ist nicht erlaubt.

Es ist offensichtlich, dass T(n,12)ist der beste Fall undT(n,0)ist der schlechteste Fall von Quicksort. Beide haben einfache Wiederholungsbeziehungen, die in jeder Bildungsressource zu finden sind. Aber ich habe keine Ahnung, wie manT(n,p)im Allgemeinen studiert. Die offensichtliche Beziehung wäre:

T(n,p)=n+T(p(n1),p)+T((1p)(n1),p)

Hier stecke ich fest. Ich habe versucht, mich umzuschauen, aber die gesamte Literatur, die ich über Divide- und Conquer-Algorithmen verstehen konnte, hat die "Divide" wörtlich genommen und die Analyse "betrogen" , indem die Partitionen immer gleich groß waren und die Begriffe zu einem Mal zusammengeführt wurden Konstante.

Ich weiß nicht, wie ich mit zwei rekursiven Aufrufen umgehen soll, und ich weiß nicht, ob es sicher ist, die Rundung zu entfernen. Ist dies analytisch zu lösen und wenn ja, wie?

PS: Ich bin in Asymptotiken nicht interessiert (was leicht ist , zu zeigen , für jeden Konstante p ). Ich interessiere mich dafür, wie viel langsamer Quicksort wird, wenn p kleiner wird, zum Beispiel interessiert mich das Verhältnis T ( n , 0,25 )Θ(nlogn)pp .T(n,0.25)T(n,0.5)

PPS: Als Student entschuldige ich mich, wenn ich offensichtliche Dinge zu langwierig oder unerklärliche Nichttrivialitäten gemacht habe. Und obwohl ich nicht weiß, ob es hier so sehr auf andere SE-Websites herabgesehen wird, werde ich feststellen, dass dies ein persönliches Interesse ist, keine Hausaufgabe.

orlp
quelle

Antworten:

9

Wie Sie erwähnen, die Akra-Bazzi - Theorem zeigt , dass die Lösung für die Wiederholung ist O ( n log n ) für alle p ( 0 , 1 ) . Dies zeigt jedoch nicht die Art der Abhängigkeit von p . Um letzteres zu bestimmen, können wir einen Rekursionsbaumansatz verwenden.T(n,p)O(nlogn)p(0,1)p

Die Wurzel des Rekursionsbaums ist das Intervall . Seine zwei Kinder sind die Intervalle { 1 , , p n } und { p n + 1 , , n } , deren Gesamtlänge wieder n ist . Jeder dieser Knoten hat zwei untergeordnete Knoten (vorausgesetzt, n ist groß genug) und so weiter. Der Einfachheit halber ignorieren wir Rundungsfehler, dh wir nehmen an, dass p n ist{1,n}{1,,pn}{pn+1,,n}nnpnist eine ganze Zahl; Dies ist nur eine technische Angelegenheit, und ich würde mir darüber keine Sorgen machen. Wir stoppen den Prozess immer dann, wenn ein Knoten höchstens Länge hat . Die Komplexität des Algorithmus ist proportional zur Gesamtlänge der Intervalle im Baum. Wenn p 1 / 2 , wobei die Blätter (Knoten , an dem wir den Prozess stoppen) unterschiedliche Tiefe aufweisen, und das macht es schwieriger , die Gesamtkomplexität zu bestimmen.1p1/2

Wir können eine einfache Obergrenze erhalten, indem wir feststellen, dass der Baum höchstens Ebenen hat: Jeder Knoten ist mindestens einen Faktor von 1 - p kleiner als sein übergeordneter Knoten . Genau wie in der Analyse für p = 1 / 2 , ist die Gesamtlänge der Intervalle auf jeder Ebene höchstens n , und wir eine obere gebundener erhalten O ( n log 1 - p ( 1 / n ) ) auf der Laufzeit. Da log 1 -log1p(1/n)1pp=1/2nO(nlog1p(1/n)) undlog(1-p ) - 1 =-log(1-p)=p±O( p 2 )für kleinespkönnen wir schreiben dies alsO(nlogn / p).log1p(1/n)=logn/log(1p)1log(1p)1=log(1p)=p±O(p2)pO(nlogn/p)

Hier ist eine genauere Berechnung. Betrachten Sie Stufe . Angenommen, wir stoppen den Prozess nicht, wenn ein kleines Intervall erreicht ist. Wir können einen zufälligen Scheitelpunkt erzeugen, indem wir t Schritte ausführen, in denen wir jeweils mit der Wahrscheinlichkeit p nach links (sagen wir) und mit der Wahrscheinlichkeit 1 - p nach rechts (sagen wir) gehen . Jedes Mal, wenn wir einen linken Schritt machen, verringert sich das Protokoll der Länge des Intervalls um - log p , und jedes Mal, wenn wir einen rechten Schritt machen, verringert es sich um - log ( 1 - p ) . Ein Scheitelpunkt befindet sich im tatsächlichen Baum des Protokolls, dessen Länge um höchstens log n verringert wurdettp1plogplog(1p)logn. Das Gesamtgewicht der Intervalle auf der Ebene des Baums ist genau die Wahrscheinlichkeit, dass ein nach diesem Prozess erzeugter Scheitelpunkt einer Abnahme von höchstens log n entspricht . Das heißt, wenn D die Verteilung ist, die gleich - log p mit der Wahrscheinlichkeit p und - log ( 1 - p ) mit der Wahrscheinlichkeit 1 - p ist und X 1 , ... , X tD unabhängig sind, dann ist das Gesamtgewicht der Ebene t isttLognD.- -Logpp- -Log(1- -p)1- -pX.1,,X.tD.t . Für die Superkonstante t ist die Zufallsvariable X 1 + + X t ungefähr normalverteilt mit dem Mittelwert [ - p log p - ( 1 - p ) log ( 1 - p ) ] t und der Varianz linear in t , also für t befriedigend [ - pPr[X.1++X.tLogn]]tX1++Xt[plogp(1p)log(1p)]ttt , sagen wir, die Wahrscheinlichkeit liegt sehr nahe bei 1 , während für t die Erfüllung von [ - p log p - ( 1 - p ) log ( 1 - p ) ] t 2 log n , sagen wir, es wird sehr nahe bei Null sein. Definieren[plogp(1p)log(1p)]t(logn)/21t[plogp(1p)log(1p)]t2logn (bekannt als binäre Entropiefunktion) schließen wir, dass die Laufzeit Θ ( n log n / h ( p ) ) (einheitlich) ist in p als n ). Als p 0 haben wir h ( p ) - p log ph(p)=plogp(1p)log(1p)Θ(nlogn/h(p))pnp0h(p)- -pLogpund so war unsere frühere Schätzung nicht eng.

Eine andere Art, dieselbe Analyse zu betrachten, besteht darin, eine unendliche Folge unabhängiger Zufallsvariablen wie zuvor zu haben und eine Stoppzeit T als das erste Mal t zu definieren, so dass X 1 + + X t ≥ ist log n . Die Laufzeit ist dann proportional zu n E [ T ] . Der elementare Erneuerungssatz besagt dann, dass lim n E [ T ] /X.1,X.2,T.tX.1++X.tLognnE.[T.]] , was bedeutet, dass die Gesamtgröße der Intervalle gleich ( 1 + o ( 1 ) ) n log n / h ( p ) ist . Genauer gesagtbeträgtfür jede Konstante p die Gesamtgröße der Intervalle ( 1 + α p ( n ) ) n log n / h ( plimnE.[T.]]/.Logn=1/.E.[D.]]=1/.h(p)(1+o(1))nlogn/h(p)p , wobei α p ( n ) = o ( n ) ist . Die Konvergenz in der Grunderneuerung Satz exponentiell in dem Zeitparameter - lügt n in unserem Fall - so sollte in Polynom n , das heißt, α p ( n ) = O ( n - C p ) . Die Konvergenz ist wahrscheinlich auch für p ( δ , 1 - δ ) für jedes δ > 0 einheitlich.(1+αp(n))nlogn/h(p)αp(n)=o(n)lognnαp(n)=O(nCp)p(δ,1δ)δ>0


Zusammenfassend hat die Gesamtlänge der Intervalle im Rekursionsbaum, die proportional zur Laufzeit ist, für jedes die folgende Form : T ( n , p ) = ( 1 + o ( 1 ) ) n log npwobeilognundh(p)=-plogp-(1-p)log(1-p)zur gleichen Basis gebracht werden undo(1)eine Funktion ist, die vonpundabhängtTendenz zu0mitn.

T(n,p)=(1+o(1))nlognh(p),
lognh(p)=plogp(1p)log(1p)o(1)p0n

Darüber hinaus ist es wahrscheinlich wahr, dass für jedes und jedes p ( δ , 1 - δ ) die Gesamtlänge der Intervalle die Form T ( n , p ) = ( 1 + O ( n -) hat C δ ) ) n log nδ>0p(δ,1δ)wobeiCδ>0und die verborgene große O-Konstante nur vonδabhängen. Insbesondere sollte es so sein, dass für alle Konstantenp1,p2, limnT(n,p1)

T(n,p)=(1+O(nCδ))nlognh(p),
Cδ>0δp1,p2 und die Konvergenz ist polynomial schnell.
limnT(n,p1)T(n,p2)=h(p2)h(p1),
Yuval Filmus
quelle
Danke für deine schnelle Antwort Yuval. Ich bin etwas verwirrt darüber, dass Sie in Ihrer Zusammenfassung verwendet haben. h ( p ) ist eine Konstante und bedeutet das nicht, dass es unter Θ irrelevant ist ? Ich beschloss, ein kleines Testprogramm zu schreiben , das zeigte, dass für n = 100000000000000 der Vergleich von T ( n , 0,1 ) / T ( n , 0,5 ) zwischen der Analysemethode und einer Berechnungsmethode einen Fehler von 0,03 ergab. Das scheint ziemlich groß zu sein, oder ist das zu erwarten? Θh(p)Θn=100000000000000T(n,0.1)/T(n,0.5)
orlp
Die Konstante in ist in p einheitlich . Genauer gesagt, für einige Konstanten c , C ist es der Fall , dass für jedes p existiert N p , so daß für n N p , C n log n / h ( p ) T ( n , p ) C n log n / h ( p ) . Sie können wahrscheinlich eine noch stärkere Aussage der Form T erhaltenΘpc,CpNpnNpcnlogn/h(p)T(n,p)Cnlogn/h(p) für jedes feste p , wobei das kleine o in Bezug auf n steht (aber von p abhängen könnte); C solltenichtvon p abhängen. T(n,p)=(1+o(1))Cnlogn/h(p)pnpCp
Yuval Filmus
Die Konvergenz zum Grenzwert hängt von . Daher muss log n möglicherweise groß sein, um eine wirklich gute Annäherung zu erhalten. Andererseits klingt ein relativer Fehler von 0,03 nicht so groß. Sie können versuchen, n zu fixieren und die Laufzeit als Funktion von p zu zeichnen , indem Sie sie mit 1 / h ( p ) vergleichen . lognlognnp1/h(p)
Yuval Filmus
Oh, tut mir leid, ich habe keinen relativen Fehler von 0,03 gemeint, sondern einen absoluten (2,13222 vs 2,10339). Das Auftragen von als Funktion von p relativ zu 1 / h ( p ) ergab eine relative Differenz von 4%, wobei T ( 10 11 , 0,05 ) h ( 0,05 ) 96% von T ( 10 11 ) betrug , 0,4 ) * h ( 0,4 ) . T(n,p)p1/h(p)T(1011,0.05)h(0.05)T(1011,0.4)h(0.4)
orlp
1
Die Superkonstante ist eine Funktion, die in Bezug auf die relevante Variable (in diesem Fall ) gegen unendlich tendiert . Es ist dasselbe wie ω ( 1 ) . nω(1)
Yuval Filmus