Comparison Sort - Theoretische

Question

Kann jemand erklären, die Lösung dieses Problems für mich?

Angenommen, Sie sind gegeben eine Sequenz von n Elemente zu Sortieren.Die input-Sequenz besteht aus n=k untersequenzen, die jeweils k Elemente.Die Elemente in einer Teilfolge sind alle kleiner als die Elemente in der nachfolgenden Folge und größer als die Elemente in der vorhergehenden Folge.Also, alle, die erforderlich ist, um Sortieren Sie die ganze Folge der Länge n ist die Art der k Elemente, die in jedem der n=k untersequenzen.Zeigen n lg k untere Schranke für die Anzahl der Vergleiche benötigt, um zu lösen diese Variante der Sortierung problem.

Lösung:

Lassen Sie S eine Sequenz von n Elemente unterteilt n/k untersequenzen jede Länge k wo alle Elemente, die in jeder Folge sind größer als alle Elemente einer vorherigen Folge und kleiner als alle Elemente von einem Erfolg Teilfolge.

Anspruch

Vergleich-basierten Algorithmus Sortieren Sortieren S müssen nehmen (n lg k) Zeit in der schlimmsten Fall.

Beweis

Zuerst bemerken, dass, wie bereits in der Hinweis-wir nicht nachweisen können, den unteren gebunden durch Multiplikation zusammen, die untere Schranken für das Sortieren von jeder Teilfolge.Das würde nur beweisen, dass es keinen schnelleren Algorithmus sortiert die untersequenzen unabhängig.Es war nicht, was wir gebeten werden zu beweisen;wir können nicht einführen zusätzliche Annahmen.

Betrachten Sie jetzt die Entscheidung, die Baum der Höhe h für den Vergleich der Art für S.Da die Elemente jeder Folge kann in beliebiger Reihenfolge sein, einer der k! Permutationen entsprechen die Letzte sortiert Auftrag einer Teilfolge.Und da gibt es n/k Z untersequenzen, von denen jede sein kann in beliebiger Reihenfolge, es gibt (k!)^n/k Permutationen S könnte, entsprechen die Sortierung von rund-Eingang um.Also jede Entscheidung Baum für die Sortierung von S müssen mindestens (k!)^n/k Blätter.Da ein binärer Baum der Höhe h nicht mehr als 2^h Blätter, wir müssen 2^h ≥ (k!)^(n/k) oder h ≥ lg((k!)^n/k).Wir daher erhalten

     h ≥ lg((k!)^n/k)          -- unbalanced parens - final one added?
       = (n/k) lg(k!)
       ≥ (n/k) lg((k/2)^k/2)
       = (n/2) lg(k/2)

Die Dritte Zeile kommt aus k! mit Ihrer k/2 größte Bedingungen mindestens k/2 jeder.(Wir implizit davon ausgegangen, dass k gerade ist.Wir könnte anpassen mit Böden und decken wenn k ungerade.)

Da gibt es mindestens einen Pfad in einem Entscheidungsbaum für die Sortierung von S, die hat die Länge mindestens (n/2) lg(k/2), das worst-case-Laufzeit von einem Vergleich-basiert Sortierung Algorithmus für S (n lg k).

Kann jemand gehen mir durch den Schritten in code block?Vor allem der Schritt, wenn lg k! wird lg((k/2)^k/2).

Answer 1

Ich habe Nachdruck der Mathematik unter:

(1) h ≥ lg(k! ^n/k)

(2) = (n/k) lg(k!)

(3) ≥ (n/k) lg((k/2)^k/2)

(4) = (n/2) lg(k/2)

Lassen Sie uns gehen Sie durch diese.Geht von Zeile (1) Zeile (2) mit Eigenschaften von Logarithmen.Ebenso gehen von Zeile (3) Zeile (4) nutzt die Eigenschaften von Logarithmen und der facththat (n / k) - (k / 2) = (n / 2).Also der trick, den Schritt von Zeile (2) Zeile (3).

Der Anspruch hier ist die folgende:

Für alle k, k!≥ (k / 2)^{(k / 2)}

Intuitiv, die Idee ist wie folgt.Betrachten k!= k(k - 1)(k - 2)...(2)(1).Wenn Sie feststellen, die Hälfte von diesen Geschäftsbedingungen sind größer als k / 2 und die Hälfte von Ihnen sind kleiner.Wenn wir fallen alle Bedingungen, die kleiner sind als k, bekommen wir etwas (in der Nähe) die folgenden:

k!≥ k(k - 1)(k - 2)...(k / 2)

Jetzt haben wir, dass k / 2 ≥ k, so haben wir, dass

k!≥ k(k - 1)(k - 2)...(k / 2) ≥ (k/2)(k/2)...(k/2)

Dies ist das Produkt von (k / 2) mit sich selbst (k / 2) - mal, so ist es gleich (k / 2)^k/2.Dieses Mathematik-nicht präzise ist, da die Logik für gerade und ungerade Werte sind ein wenig anders, aber im wesentlichen mit dieser Idee erhalten Sie eine Skizze des Beweises von dem früheren Ergebnis.

Um zusammenzufassen:aus (1) bis (2) und (3) zu (4) nutzt die Eigenschaften von Logarithmen, und aus (2) bis (3) verwendet, um das obige Ergebnis.

Hoffe, das hilft!