Das Nachschlagen in einer unsortierten Liste ist eine zeitaufwändige Aufgabe . Wenn die Liste jedoch sortiert ist, ist die zeitliche Komplexität gleich. Das heißt, es lohnt sich manchmal, ein Array zu sortieren. Dies ist jedoch ein Kompromiss, da ein Sortieralgorithmus eine zeitliche Komplexität von hat.
Soweit ich weiß, können Sie ein Array nicht in weniger als sortieren Zeit. Ich frage mich jedoch, ob es einen Algorithmus gibt, der das Array teilweise in kürzerer Zeit sortieren kann . Ich bin mir ziemlich sicher, dass Sie einen Wert in einem so teilweise sortierten Array in nicht nachschlagen können Zeit, aber kannst du es besser machen als ?
Kurz gesagt, ist es möglich, ein unsortiertes Array mit einem Algorithmus schneller als zu verarbeiten so dass ein Suchalgorithmus eine Suche schneller als durchführen kann , wenn auch nicht so schnell wie ?
quelle
O(nlog(n))
, sodass ein Suchalgorithmus eine Suche schneller durchführen kann alsO(n)
" Vielleicht. "Kann eine teilweise Sortierung bei den Suchkosten in Arrays helfen?" Absolut nicht (für eine einzelne Suche).Antworten:
Wenn Sie "Balanced Quicksort" (unter Verwendung des exakten Medians bei jedem Schritt) bis zur Tiefe ausführenk (auf Kosten von O(nk) ) erhalten Sie eine Partition des ursprünglichen Arrays in 2k sortierte Teile von n/2k jeweils unsortierte Elemente. Wenn ein Element gegeben ist, können wir das richtige Teil rechtzeitig findenO(log(2k))=O(k) Verwenden Sie die binäre Suche und suchen Sie sie dann mit einer zusätzlichen O(n/2k) für eine Gesamtkomplexität von O(n/2k+k) .
Wennk=o(logn) dann braucht die Teilsortierung Zeit o(nlogn) . Wennk=ω(1) dann braucht der Suchalgorithmus Zeit o(n) . Also wenn1≪k≪logn wir bekommen o(nlogn) Vorverarbeitungszeit und o(n) Suchzeit. Zum Beispiel wennk=loglogn dann dauert die Vorverarbeitung O(nloglogn) und Nachschlagen dauert O(n/logn) .
quelle
std::partial_sort
implementiert.