ungefähre nächste Nachbarn Zeit Komplexität

Question

Ich lese dieses Papier Product quantization for nearest neighbor search.

Auf der letzten Zeile der Tabelle II Seite 5 gibt es

die Komplexität in dieser Tabelle für die Suche die k kleinsten Elemente ist die durchschnittliche Komplexität für n >> k und wenn die Elemente willkürlich geordnete

die n+klogkloglogn ist.

Ich denke, wir können lineare Auswahlalgorithmus verwenden, unsortierte k nächsten Nachbarn mit O(n) zu bekommen, und sortieren die k nächsten Nachbarn mit O(klogk), so können wir O(n+klogk) insgesamt haben. Aber woher kommt der loglogn Begriff?

Das Papier gibt einen Hinweis auf das TAOCP Buch dafür, aber ich habe das Buch nicht zur Hand, könnte mir jemand das erklären?

Answer 1

Zunächst wird in Tabelle II die Komplexität jedes Schritts angegeben. Daher müssen Sie alle Begriffe hinzufügen, um die Komplexität von ADC zu messen.

In der letzten Zeile der Tabelle ist es eine einzige Komplexität sowohl für SDC und ADC, das:

n + k log k log log n

Der Begriff entspricht die durchschnittlichen algorithmischen Kosten des Auswahlalgorithmus, den wir verwenden, um die k kleinsten Werte in einer Menge von n Variablen zu finden, die wir aus Donald Knuths Buch [25] kopieren/einfügen.

Ich habe das Buch nicht in Händen, ich kann nicht überprüfen, aber es klingt richtig.

---

_{Von den Autoren}