Ich lerne gerade grundlegende Algorithmen für Big Oh. Ich habe mich gefragt, ob jemand mir zeigen kann, was der Code für (n log n) in Java mit Big Oh wäre, oder mich auf irgendeine SO-Seite verweisen würde, wo eine existiert.
Da ich nur ein Anfänger bin, kann ich mir den Code nur vorstellen, bevor ich ihn schreibe. Also, theoretisch (zumindest) sollte es eine for-Schleife enthalten, in der wir etwas n-mal haben. Dann können wir für die log n die while-Schleife verwenden. Also wird die Schleife n-mal ausgeführt und die while-Schleife wird zweimal in der log-Basis ausgeführt. Zumindest stelle ich mir das in meinem Kopf vor, aber wenn ich den Code sehe, würde das alles klären.
Erklärung:
Die äußere for-Schleife sollte klar sein. Es wird n mal ausgeführt. Jetzt zur inneren Schleife. In der inneren Schleife nehmen Sie einfach n und teilen sie immer durch 2 . also fragst du dich: Wie oft kann ich n durch 2 teilen.
Es stellt sich heraus, dass dies in O (log n) ist. (In der Tat ist die Basis von log 2 , aber in Big-Oh Notation verlassen wir die Basis, da es nur einige Faktoren zu unserem Protokoll hinzufügen würde, an denen wir nicht interessiert sind).
Sie führen also eine Schleife n mal aus und innerhalb dieser Schleife führen Sie eine weitere Schleife log(n) mal aus, so dass Sie O(n) * O(log n) = O(n log n) haben.
Ein sehr beliebter O (n log n) -Algorithmus ist merge sort. Ссылка zum Beispiel des Algorithmus und Pseudocode. Der log n-Teil des Algorithmus wird erreicht, indem das Problem in kleinere Teilprobleme zerlegt wird, in denen die Höhe des Rekursionsbaums log n ist.
Viele Sortieralgorithmen haben die Laufzeit von O (n log n). Weitere Beispiele finden Sie unter Ссылка .
Algorithmen mit einer O(.) -Zeitkomplexität, die log n beinhalten, beinhalten typischerweise eine Art von Divide and Conquer.
Zum Beispiel wird in MergeSort die Liste halbiert, jeder Teil wird einzeln zusammengeführt und dann werden die beiden Hälften geteilt zusammengeführt. Jede Liste wird halbiert .
Immer wenn Ihre Arbeit um einen bestimmten Faktor halbiert oder verkleinert wird, erhalten Sie normalerweise eine log n -Komponente von O(.) .
Schauen Sie sich in Bezug auf den Code den Algorithmus für MergeSort an. Das wichtige Merkmal typischer Implementierungen ist, dass es rekursiv ist (beachte, dass TopDownSplitMerge sich selbst zweimal in dem auf Wikipedia angegebenen Code aufruft).
Alle guten Standardsortieralgorithmen haben O(n log n) Zeitkomplexität und es ist im schlechtesten Fall nicht möglich, es besser zu machen, siehe Vergleichssortierung .
Um zu sehen, wie dies im Java-Code aussieht, suchen Sie ! Hier ist ein Beispiel .