Komplexität beim Finden der größten Zahlen in einem Array der Größe

Was folgt, ist mein Algorithmus, um dies in einer Zeit zu tun, von der ich glaube, dass sie ist, und mein Beweis dafür. Mein Professor ist anderer Meinung, dass es in läuft und denkt stattdessen, dass es in läuft . Alle Kommentare bezüglich des Beweises selbst oder des Stils (dh meine Ideen mögen klar sein, die Präsentation jedoch nicht).$O(n)$$O(n)$$\Omega(n^2)$

Die ursprüngliche Frage:

Gegeben Zahlen, finden Sie die größte unter ihnen in der Zeit . Sie dürfen nichts anderes über annehmen .$n$$m \leq n$$o(n \log n)$$m$

Meine Antwort:

1. Sortieren Sie die ersten Elemente des Arrays. Dies dauert , da dies vollständig von und nicht von abhängt .$m$$O(1)$$m$$n$
2. Speichern Sie sie in einer verknüpften Liste (unter Beibehaltung der sortierten Reihenfolge). Dies dauert aus dem gleichen Grund wie oben auch .$O(1)$
3. Testen Sie für jedes andere Element im Array, ob es größer als das kleinste Element der verknüpften Liste ist. Dies dauert Zeit, da Vergleiche durchgeführt werden müssen.$O(n)$$n$
4. Wenn die Anzahl tatsächlich größer ist, löschen Sie das erste Element der verknüpften Liste (das niedrigste) und fügen Sie die neue Nummer an der Stelle ein, an der die Liste in sortierter Reihenfolge gehalten werden soll. Dies dauert da es durch eine Konstante ( ) oben begrenzt ist, da die Liste nicht wächst.$O(1)$$m$
5. Daher ist die Gesamtkomplexität für den Algorithmus .$O(n)$

Mir ist bewusst, dass die Verwendung eines rot-schwarzen Baums im Gegensatz zu einer verknüpften Liste in konstanter Hinsicht effizienter ist (da die konstante Obergrenze im Gegensatz zu und das Problem, einen Zeiger zu behalten Das unterste Element des Baumes (um die Vergleiche zu erleichtern) ist hervorragend machbar, es ist mir damals einfach nicht in den Sinn gekommen.$O(m\cdot \log_2(m))$$m$

Was fehlt mein Beweis? Gibt es eine Standardmethode für die Darstellung (auch wenn sie falsch ist)?

Hier ist ein -Algorithmus, der das Problem löst.$O(n)$

1. Verwenden Sie den -Auswahlalgorithmus im ungünstigsten Fall , um die Statistik ter Ordnung zu bestimmen . Sei diese Zahl, die kleinste der größten Zahlen, die wir zu bestimmen versuchen.$O(n)$ $n-m+1$$k$$m$

2. Partitionieren Sie nun das Array mit der QuickSort- Partitionsfunktion um den Pivot . Dieser Schritt benötigt auch .$k$$O(n)$

3. Geben Sie die größten Zahlen aus: Diese werden durch und alle Zahlen im oberen Subarray angegeben, die durch die Partition in Schritt 2 generiert wurden.$m$$k$

Ihr Algorithmus dauert $\Theta(n + mn)$Zeit. Ich vermute, dass Ihr Professor nach etwas sucht, das braucht$O(n+ n\log m)$ Zeit, die möglich sein sollte, vielleicht mit einem Haufen ...

Die Ursache für Ihre Meinungsverschiedenheit mit dem Professor ist, dass er oder sie nicht zu denken scheint $m$ist eine Konstante, trotz des Wortlauts der Frage. Wenn nicht, dann$\Theta(m)$ ist viel schlimmer als $\Theta(\log m)$.

Korrektheit In
Ihrer Präsentation fehlt die Schleife, um die Korrektheit festzustellen: Sie behalten die größte bei$m$Elemente, die bisher in einer verknüpften Liste angetroffen wurden. Somit haben Sie am Ende Ihres Algorithmus alle Elemente getestet und haben somit das größte$m$Elemente im Array. Ihr Algorithmus ist immer noch korrekt, aber die Angabe des Zwecks der verknüpften Liste am Anfang der Beschreibung macht die Richtigkeit deutlicher.

Laufzeit
$log_{10}( 10 \mbox{ billion}) = 10$, (mit Basis 2 sind es ungefähr ~ 33), was viel kleiner als 10 Millionen ist. In dem angegebenen Beispiel$m$ ist um ein Vielfaches größer als $\log n$und deshalb glaube ich nicht, dass Sie das sicher annehmen können $m$ ist konstant.

Sie sollten einen Algorithmus bereitstellen, der ist $o(n \log n)$ so lange wie $m = o(n)$. Durch Ersetzen Ihrer verknüpften Liste und linearen Suche durch einen ausgeglichenen binären Suchbaum oder einen Min-Heap wird diese Laufzeit erreicht:$O(m \log m + n \log m) = O(n \log m) = o(n \log n)$. (unter der Annahme$m = o(n)$, sonst ist deine Laufzeit $\Theta(n \log n)$)

Falls Sie mit der Notation und der dahinter stehenden Intuition nicht vertraut sind $o(n \log n)$ ist $< O(n \log n)$Einzelheiten zur Notation finden Sie in der entsprechenden Frage auf cs.SE.