Prüft die Collections.sort(list) ob die list bereits sortiert ist oder ist es vielleicht O (1) aus einem anderen Grund?
Oder ist es eine gute Idee, eine Flagge sortiert zu haben und sie auf true/false nach dem Aufruf sort()/ein Element auf der Liste hinzufügen?Java - Ruft sort() auf eine bereits sortierte Liste eine O (1) -Operation auf?
Wie können Sie feststellen, ob eine Liste sortiert ist, ohne sie anzusehen? Es wird nicht O(1) sein. Das Ermitteln, ob eine Liste sortiert ist, dauert mindestens O(n).
Das würde bedeuten Wenn Collections.sort müßte um zu überprüfen, ob eine Liste zuerst sortiert wurde, würde jeder Sortiervorgang einen Durchschnitt von O(n) + O(n log n) nehmen.
Es gibt keine Möglichkeit, es ist O (1), Sie können nicht überprüfen, ob die Sammlung schneller als O (n) sortiert ist. Eine Flagge zu haben sollte in Ordnung sein, aber schwer zu sagen, ohne zu wissen, was genau du machst.
Im Allgemeinen macht das Sortieren einer bereits sortierten Liste es nicht schneller (außer einfache Sortierungen wie bubble sort). In einigen Fällen ist vorsortiert langsamer.
Im Fall von Collections.sort() ist es nicht schneller, eine sortierte Liste zu sortieren.
Eigentlich nicht ganz wahr. iirc Java benutzt Timsort für einige Dinge, die mit Java7 beginnen, und Timsort ist ziemlich gut darin, teilweise sortierte Listen zu sortieren, dh besser als das theoretische 'O (n log n)' – Voo
+1 für vorsortierte langsamer in einigen Fällen –
Tatsächlich hat Java für einige Sortieraufgaben von mergesort zu TimSort gewechselt (benannt nach Python-Entwickler Tim Peters, der es für cpython zuerst implementiert hat).
Während es nicht O (1) ist, ist das Sortieren einer bereits sortierten oder teilweise sortierten Liste mit TimSort effizienter als das Sortieren eines komplett zufälligen Datensatzes (für den späteren Fall gibt es keine Möglichkeit effizienter zu sein als O(n log n) für Vergleichssorten) , das gilt nicht für nicht zufällige Daten).
Ok, aber die Wahrscheinlichkeit, dass die Person, die fragt, Java 7 verwendet, ist ziemlich niedrig (manche sagen 18% http://blog.jelastic.com/2011/12/07/java-7-adoption-grows-to-18-percent/) –
@vitalik Die Wahrscheinlichkeit, dass zukünftige Leser Java 7 oder später verwenden werden, kann nur von dort aus zunehmen. SO ist als Informationsarchiv gedacht, nicht als Forum. – EJP
@EJP Wenn man bedenkt, dass vitalik meinen Beitrag nicht abgelehnt hat, als er diesen Kommentar gepostet hat, haben Sie versehentlich einen falschen Mausklick gemacht? Sonst bin ich ziemlich überrascht, dass irgendjemand meinen Beitrag ablehnen würde. b2t: Ich denke, solange ich explizit erwähne, dass das nur für Java7 gilt + wie viele Leute welche Version benutzen ist nicht allzu wichtig - 18% sind noch ziemlich viele Leute. – Voo
streng genommen bedeutet O (1) nicht 1 Index :) – unbeli
@unbeli +1 korrigiert meine Antwort. – Aidanc
Und 'O (n) + O (n log n)' ist das gleiche wie 'O (n log n)' :) – unbeli