Durchschnittliche Zeitkomplexität zum Auffinden von Top-K-Elementen

Question

Betrachten Sie die Aufgabe, die Top-k-Elemente in einer Menge von N unabhängigen und identisch verteilten Gleitkommawerten zu finden. Durch die Verwendung einer Prioritätswarteschlange/Heap, können wir einmal über alle N Elemente iterieren und eine Top-k durch die folgenden Operationen eingestellt halten:

• , wenn das Element x „schlechter“ als der Kopf des Heap: Verwerfungs x ⇒ Komplexität O (1)

• wenn das Element x ist "besser" als der Kopf des heap: den Kopf entfernen, und legen x ⇒ Komplexität O (log k)

die ungünstigste Zeitkomplexität von Dieser Ansatz ist offensichtlich O (N log k), aber was ist mit der durchschnittlichen Zeitkomplexität? Aufgrund der iid-Annahme, die Wahrscheinlichkeit der O (1) Betrieb erhöht sich im Laufe der Zeit, und wir haben nur selten die teure O durchführen (log k), insbesondere für k < < N.

Ist das durchschnittliche Zeit Komplexität dokumentiert in jeder zitierbaren Referenz? Wie hoch ist die durchschnittliche Zeitkomplexität? Wenn Sie eine Referenz für Ihre Antwort haben, fügen Sie sie bitte hinzu.

Answer 1

Betrachten Sie das i'th größte Element und eine bestimmte Permutation. Es wird in den k-großen Heap eingefügt, wenn es vor nicht mehr als k-1 der (i - 1) größeren Elemente in der Permutation erscheint.

Die Wahrscheinlichkeit, dass die Heap-Insertion stattfindet, ist 1, wenn i < = k und k/i, wenn i> k.

Daraus können Sie die Erwartung der Anzahl der Heap-Anpassungen berechnen, wobei die Linearität der Erwartung verwendet wird. Es ist Summe (i = 1 bis k) 1 + Summe (i = k + 1 bis n) k/i = k + Summe (i = k + 1 bis n) k/i = k * (1 + H (n) - H (k)), wobei H (n) die n-te harmonische Zahl ist.

Dies ist ungefähr k log (n) (für k < < n), und Sie können Ihre durchschnittlichen Kosten von dort berechnen.