Wie kann ich sagen, dass die zeitliche Komplexitätsreihenfolge eines Algorithmus O (N log N) ist?

22

Mit welchem ​​Begriff kann ich etwas mit O (N log N) -Komplexität beschreiben?

Beispielsweise:

  • O (1): Konstante

  • O (log N): Logarithmisch

  • O (N): linear

  • O (N log N): ??????

  • O (N 2 ): Quadratisch

  • O (N 3 ): kubisch

algorithms algorithm-analysis big-o matiascelasco
quelle
5
Ich meine hier oft den weiten Begriff "quasi linear" O(n · f(n))wo f(n) << n. Dies passt aber auch zu Dingen wie O(n · log log n)und O(n α(n))wo α(n)ist die Umkehrung der Ackermann-Funktion.
Bakuriu
en.wikipedia.org/wiki/…
Ry-
34
"Oh enn log enn" ist wahrscheinlich gut genug.
user253751
Standortübergreifendes Duplikat hier: Wie heißt die von O (n log n) beschriebene Funktionsklasse?
Martin

Antworten:

60

"N log N" ist so gut wie nie zuvor und sollte von professionellen Programmierern verstanden werden. Sie können nicht erwarten, dass es ein einziges Wort gibt, das jede existierende Komplexitätsklasse beschreibt.

Philip Kendall
quelle
6
"Ich kann nicht erwarten, dass es ein einziges Wort gibt, das jede Komplexitätsklasse beschreibt" - sicherlich nicht. Aber 𝓞 ( n ⋅ log n ) ist eine so wichtige Klasse, dass es einen eigenen Namen verdient, IMO; und wie von Steve Jessop gesagt, ist Linearithmus bereits ziemlich verbreitet.
links ungefähr
@leftaroundabout Es ist in der Tat häufig genug, dass Sie argumentieren könnten, dass es einen Namen verdient. Aber "n log n" ist kurz genug, um auszusprechen (nur drei Silben), dass es als Name gut funktioniert. Zum Vergleich: "Logarithmisch" besteht aus vier Silben. Interessanter ist es, wenn Sie zu externen Algorithmen gelangen, bei denen die meisten "n log n" -Algorithmen Komplexität aufweisen ($ N log_B (N / B) $). Dies wäre sicherlich eine Komplexitätsklasse, die einen kürzeren Namen verdient.
Kasperd
10
Als Informatik-Masterstudent habe ich während meines Studiums "enn log enn" gehört. Ich habe noch nie "linearithmisch" gehört und würde zunächst nicht verstehen, was das bedeutet.
Kevin - Reinstate Monica
@ Kevin: Logarithmisch sind vier Silben, aber "log-enn" ist nur zwei. Ebenso ist O (N ^ 2) "enn-quadriert", nicht "quadratisch". Ich nehme an, "cubic" hat weniger Phoneme als "enn-cubed", aber ich denke, der letztgenannte Begriff würde immer noch häufiger vorkommen.
Supercat
51

Es gibt einen Jargonbegriff linearithmisch , der genau dies bedeutet.

Ich glaube nicht, dass es von allen Programmierern allgemein verstanden wird. Wenn Sie also nicht aufpassen, wird es mehr verdecken, als es aussagt. Persönlich verwende ich es normalerweise nicht, und wenn ja, würde ich es wahrscheinlich bei der ersten Verwendung definieren, zum Beispiel "dieser Artikel berücksichtigt linearithmische ( O(N log N)) Algorithmen".

Steve Jessop
quelle
11
Ich wusste gar nicht, dass es das gibt!
David sagt Reinstate Monica
12

Es wird manchmal als "loglinear" bezeichnet, obwohl dieses Wort tatsächlich etwas anderes bedeutet. Ich würde mich aber einfach an "N log N" halten, wie die Antwort von @ Philip nahelegt.

Jörg W. Mittag
quelle
1
Was ist die alternative Bedeutung für log-linear? Wenn ich einen anderen Namen als 'N log N' haben wollte, würde ich den Begriff log-linear verwenden.
Jonathan Leffler
2
@ JonathanLeffler: Ich gehe davon aus, dass en.wikipedia.org/wiki/Log-linear_analysis manchmal ohne Bindestrich geschrieben wird. Natürlich könnten Sie mit dem richtigen Namensraum das gleiche Wort für eine Komplexitätsklasse verwenden.
Steve Jessop
@SteveJessop: Genau das ist über eine Google-Suche herausgekommen. Ich bin nicht sicher, ob ich bereit bin, die Google / Wikipedia-Kombination als maßgeblich zu akzeptieren, obwohl ich keinen Zweifel daran habe, dass die logarithmische lineare Analyse der Beschreibung entspricht.
Jonathan Leffler
1
@ JonathanLeffler: könnte auch bedeuten, was ich als Lin-Log- oder Log-Lin-Plot bezeichne (oder, weil ich faul bin, würde ich sie oft als Log-Plot bezeichnen, anders als ein Log-Log-Plot). Vielleicht fragen wir uns, welche alternative Bedeutung diese Antwort hat :-)
Steve Jessop
2

Da der Faktor log nlangsam wächst, wäre eine qualitative Beschreibung für O(n log n)"fast linear". Abhängig von Ihrer Zielgruppe ist die Klasse der O(n log n)Algorithmen möglicherweise gut bekannt, wie dies beispielsweise bei der schnellen Sortierung von nElementen durch Vergleiche der Fall ist .

Hardmath
quelle