Kann eine teilweise Sortierung bei den Suchkosten in Arrays helfen?

7

Das Nachschlagen in einer unsortierten Liste ist eine zeitaufwändige Aufgabe O(n). Wenn die Liste jedoch sortiert ist, ist die zeitliche Komplexität gleichO(log(n)). Das heißt, es lohnt sich manchmal, ein Array zu sortieren. Dies ist jedoch ein Kompromiss, da ein Sortieralgorithmus eine zeitliche Komplexität von hatO(nlog(n)).

Soweit ich weiß, können Sie ein Array nicht in weniger als sortieren O(nlog(n)) 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önnenO(log(n)) Zeit, aber kannst du es besser machen als O(n)?

Kurz gesagt, ist es möglich, ein unsortiertes Array mit einem Algorithmus schneller als zu verarbeiten O(nlog(n)) so dass ein Suchalgorithmus eine Suche schneller als durchführen kann O(n), wenn auch nicht so schnell wie O(log(n))?

SE - hör auf, die Guten zu feuern
quelle
Ich bin mir bewusst, dass es irgendwo einen sehr grundlegenden Fehler oder ein Missverständnis geben kann, ich bin nicht und habe noch nie Informatik studiert, und ich fühle mich mit dem nicht wohl ONotation.
SE - hör auf, die Guten zu feuern
2
Sie können eine Liste sortieren O(nlogn)Zeit.
Rick Decker
1
Es ist ein bisschen unklar, wonach genau Sie suchen, aber nehmen Sie eine QuickSort-Median-Pivot-Version (funktioniert garantiert in nlogn im Austausch für Median-Overhead. Führen Sie nun die Hälfte der Schritte aus. Was gibt Ihnen das? Daten sind partitioniert und in Die Elemente jeder Partition sind nicht weit vom sortierten Index entfernt, aber während der Suche müssen Sie eine Partition durchlaufen.
Evil
2
Bitte definieren Sie, was genau Sie unter "teilweise sortiert" verstehen. In der Literatur gibt es viele konkurrierende Begriffe von Sortierung.
Raphael
1
"Ist es möglich, ein unsortiertes Array mit einem Algorithmus schneller als diesem zu verarbeiten O(nlog(n)), sodass ein Suchalgorithmus eine Suche schneller durchführen kann als O(n)" Vielleicht. "Kann eine teilweise Sortierung bei den Suchkosten in Arrays helfen?" Absolut nicht (für eine einzelne Suche).
Mooing Duck

Antworten:

12

Wenn Sie "Balanced Quicksort" (unter Verwendung des exakten Medians bei jedem Schritt) bis zur Tiefe ausführen k (auf Kosten von O(nk)) erhalten Sie eine Partition des ursprünglichen Arrays in 2k sortierte Teile von n/2kjeweils 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).

Wenn k=o(logn) dann braucht die Teilsortierung Zeit o(nlogn). Wennk=ω(1) dann braucht der Suchalgorithmus Zeit o(n). Also wenn1klogn 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).

Yuval Filmus
quelle
2
Wenn der ausgeglichene Quicksort den Zielwert kennt und nur auf der Seite mit dem Zielwert rekursiv ist, ist die Zeit ~ 4n, um die volle Tiefe zu erreichen. So wird C ++ std::partial_sortimplementiert.
Mooing Duck
Eine Alternative ist die unvollständige Radix-Sortierung. Die Vorverarbeitungszeit kann schneller sein, es gibt jedoch weniger Kontrolle über die Schaufelgrößen. Ein ähnlicher Kommentar kann zum Präfix Perfect Hashing abgegeben werden.
Eric Towers