Frage 1: Ist das in O (n)?
Das ist richtig (hier bezeichnet n die Länge jedes der beiden Arrays).
Ist es wichtig, wie viele Schleifen (nicht verschachtelte Schleifen) in Methode 1 sind?
Dies ist nicht der Fall, solange die Anzahl der Schleifen fest ist und die Anzahl der Iterationen in jeder Schleife in n linear ist. Formal ausgedrückt, wenn C eine Konstante ist, ist C*n O(n) .
Frage 2: Was ist, wenn es ein
gibt?Arrays.sort(a);
Die Sortierung erfolgt normalerweise O(n logn) , und dies ist Arrays.sort(int[]) macht im Durchschnitt . Die Dokumentation ist vage über die Worst-Case-Leistung:
Dieser Algorithmus bietet O (n log (n)) -Leistung für viele Datensätze, die andere Quicksorts zu einer quadratischen Leistung führen, und ist in der Regel schneller als herkömmliche QuickSort-Implementierungen (ein Pivot).
Dies garantiert deutlich, dass O(n logn) im worst case nicht garantiert ist. Das Lesen zwischen den Zeilen deutet darauf hin, dass es wahrscheinlich O(n^2) ist.
Es ist interessant zu bemerken, dass in JDK7 Arrays.sort(Object[]) verwendet einen anderen Algorithmus als der von Arrays.sort(int[]) . Ersteres ist eine Anpassung von TimSort und sollte daher% code% der Worst-Case-Leistung garantieren. Leider hört die Dokumentation wieder auf, dies nicht zu buchstabieren.
a. Es ist O (n) wobei n = Länge der Eingabe (gesamt)
b. Ja, es ist wichtig, wie viele Schleifen es gibt: Wenn es eine konstante Anzahl von Schleifen k ist, dann ist es O (k * n), das normalerweise als O (n) betrachtet wird, aber wenn k & gt; = n ist, sollte etwas berücksichtigt werden / p>
Arrays.sort(a); wird mit merge sort implementiert, das in O (n log n) sowohl im Durchschnitt als auch im schlimmsten Fall läuft (nicht wie NPE sagte!).
Update für MrSmith42:
Von Ссылка :
der Algorithmus sort (Object []) muss kein MergeSort sein, muss aber stabil sein.)
Und auch:
Implementierungshinweis: Der Sortieralgorithmus ist ein Dual-Pivot Quicksort von Vladimir Yaroslavskiy, Jon Bentley und Joshua Bloch. Dieser Algorithmus bietet O (n log (n)) -Leistung für viele Datensätze, die andere Quicksorts zu einer quadratischen Leistung führen, und ist in der Regel schneller als herkömmliche (ein Pivot) Quicksort-Implementierungen.