Erwartete Zeit von Quicksort

Ich lese den Beweis des Theorems:

Der Algorithmus Quicksort sortiert eine Folge von$n$Elemente hinein$O(n \log n)$erwartete Zeit.

Der Beweis ist dieser:

Der Einfachheit halber wird bei der Timing-Analyse davon ausgegangen, dass alle Elemente von$S$sind verschieden.

Diese Annahme maximiert die Größen von$S_1$Und$S_3$, und maximieren daher die durchschnittliche Zeit, die in den rekursiven Aufrufen verbracht wird (QUICKSORT($S_1$), SCHNELLE SORTE($S_3$)).

Lassen$T(n)$sei die erwartete Zeit, die QUICKSORT benötigt, um eine Folge von zu sortieren$n$Elemente.

Deutlich,$T(0)=T(1)=b$für einige konstant$b$.

Nehmen Sie dieses Element an$a$(der Pivot, der zufällig ausgewählt wird) ist das i-te kleinste Element des$n$Elemente in Sequenzen.

Dann die beiden rekursiven Aufrufe von QUICKSORT (QUICKSORT($S_1$), SCHNELLE SORTE($S_3$)) haben eine erwartete Zeit von$T(i-1)$Und$T(n-i)$, bzw.

Seit$i$mit gleicher Wahrscheinlichkeit einen beliebigen Wert dazwischen annimmt$1$Und$n$, und der Saldo von QUICKSORT($S$erfordert eindeutig Zeit$cn$für einige konstant$c$, haben wir die Beziehung:

$$T(n) \leq cn +\frac{1}{n} \sum_{i=1}^{n} [T(i-1)+T(n-i)], \text{ for } n\geq 2 \tag {1}$$

Algebraische Manipulation von$(1)$Erträge

$$T(n) \leq cn +\frac{2}{n}\sum_{i=0}^{n-1}T(i) \tag {2}$$

Wir werden das für zeigen$n \geq 2$,$T(n) \leq kn \log_e n$, Wo$k=2c+2b$Und$b=T(0)=T(1)$.

Für die Grundlage$n=2$,$T(2)\leq 2c+2b$folgt unmittelbar aus$(2)$.

Schreiben Sie für den Induktionsschritt$(2)$als

$$T(n) \leq cn +\frac{4b}{n}+\frac{2}{n}\sum_{i=2}^{n-1} k i \log_e i \tag {3}$$

Seit$i \log_e i$nach oben konkav ist, kann man das leicht zeigen

$$\sum_{i=2}^{n-1} i \log_e i \leq \int_2^n x \log_e x dx \leq \frac{n^2 \log_e n}{2}-\frac{n^2}{4} \tag {4}$$

Ersetzen$(4)$In$(3)$Erträge

$$T(n) \leq cn+\frac{4b}{n}+kn \log_e n-\frac{kn}{2} \tag {5}$$

Seit$n\geq 2$Und$k=2c+2b$, es folgt dem$cn+4b/n\leq kn/2$.

Daher$T(n)\leq kn \log_e n$folgt$(5)$.

Wie sind wir auf die Relation gekommen$(1)$?

Vielen Dank im Voraus.

Bearbeiten:

Können Sie mir diesen Satz erklären:

"Diese Annahme wird die Größen von maximieren$S_1$Und$S_3$, und maximieren daher die durchschnittliche Zeit, die in den rekursiven Aufrufen verbracht wird (QUICKSORT($S_1$), SCHNELLE SORTE($S_3$)). "

?

Warum maximiert dies die durchschnittliche Zeit, die in den rekursiven Aufrufen verbracht wird?