Ich lese dieses Papier Product quantization for nearest neighbor search.ungefähre nächste Nachbarn Zeit Komplexität
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?
Es scheint nur eine schlechte Tabellenformatierung. Die "Finde die k kleinsten Abstände" ist für SDC "n + k log k" und für ADC "log log n". Da die Spalten zu nahe beieinander liegen, liest man sie zusammen als "n + k log k log log n" – user31264
@ user31264 danke! Ich habe auch darüber nachgedacht, aber eine Log-Log-n-Zeit-Komplexität macht für mich noch weniger Sinn. – dontloo
@ user31264 und dontloo, können Sie bitte einen Blick auf meine [Frage] (http://stackoverflow.com/questions/38382217/k-reproduction-values)? – gsamaras