Wie heißt die von O (n log n) beschriebene Funktionsklasse?

40

In "Big O" haben allgemeine Notationen allgemeine Namen (anstatt "Oh eines konstanten Faktors" zu sagen):

O (1) ist "konstant"

O (log n) ist "logarithmisch"

O (n) ist "linear"

O (n ^ 2) ist "quadratisch"

O (n * log n) ist ???

Ist es nur "n log n" oder hat es einen speziellen Namen wie oben?

terminology asymptotics GlenPeterson
quelle
4
Standortübergreifendes Duplikat als Referenz: Wie kann ich sagen, dass die zeitliche Komplexitätsreihenfolge eines Algorithmus O (N log N) ist?
Philip Kendall

Antworten:

52

Es heißt linearithmische Zeit und ist ein Spezialfall einer allgemeineren Klasse, die als quasi linear bekannt ist . Wie der Name vermuten lässt, laufen die Algorithmen, die in diese Klasse fallen, fast in linearer Zeit ab. Tatsächlich haben sie eine geringere Komplexität als Algorithmen, die in mit laufen .O(nk)k>1

Roukah
quelle
Kommentare sind nicht für längere Diskussionen gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Gilles 'SO- hör auf böse zu sein'
17

linearithmisch

Von einem Algorithmus mit einer Laufzeit von O (N log N). Von Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7) als Portmanteau von 'linear' und 'logarithmisch' in Algorithms In C geprägt.

http://catb.org/jargon/html/L/linearithmic.html

miracle173
quelle
Warum wundert es mich nicht, dass es von Sedge kommt ... :)
TextGeek
11

Ich habe immer gehört, dass O (n log n) als "log-linear" beschrieben wurde, was mir ungefähr richtig erscheint.

Dylan Skola
quelle
4
Das heißt, eine Referenz oder zwei wäre schön.
Raphael
7

Das war zu lang für einen Kommentar, also schrieb ich eine Antwort. Ich habe dies nicht zu meiner ersten Antwort hinzugefügt, da viele Leute bereits meinen ersten Lieferwagen bewertet haben und ich nicht sicher bin, ob sie dieser Antwort auch zustimmen.

  • Ich denke nicht, dass Linearithmus ein gut etablierter Begriff ist, wie in einem Kommentar zur akzeptierten Antwort angegeben. Ich habe einige ziemlich junge Artikel mit diesem Begriff gegoogelt, einen CS-Kurs und ein weiteres Buch von Sedgewick, das diesen Begriff und viele Online-Wörterbücher verwendet.
  • Den Begriff quasilinear fand ich in zwei Artikeln:

    Die Erfüllbarkeit ist quasilinear vollständig im NQL
    CP Schnorr
    Journal der Association for Computing Machinery,
    Band 25. Nr. 1, Januar 1978, S. 136-1,15

und in einem in der Wikipedia zitierten Artikel, der sich mit diesem Schorr-Artikel befasst. Schnorr führt die Komplexitätsklassen Quasilinear (QL) und Nichtdeterministic Quasilinear (NQL) ein.
Quasilinear scheint auch in der Theorie der partiellen Differentialgleichungen verwendet zu werden.

Alles in allem scheint es, dass ein oder mehrere Wikipedianer Namen für diese Funktion angeben wollten, die keinen allgemein akzeptierten Namen haben. Aber selbst jetzt scheint es mir, dass keiner der Namen allgemein akzeptiert wird (abgesehen davon denke ich, dass dies eine Art Manipulation ist, die Wikipedia nicht tun sollte). Ich denke, man muss vorsichtig sein, wenn man Wikipedia für terminologische Fragen verwendet. Und für diese Funktion ist es keine ausreichende Quelle. Ich denke, der einzige weit verbreitete Name für diese Funktion ist n log n .

miracle173
quelle
1
Während die Legitimität von linearithmisch und loglinear umstritten sein mag, glaube ich, dass quasi-linear ein gut etablierter Begriff ist. Es scheint in Forschungsarbeiten weit verbreitet zu sein.
Roukah
@ Roukah ja, aber es bedeutet nicht ganz dasselbe; quasilinear ist allgemeiner. - Ich sehe nicht , was los ist mit Wikipedia einen Namen, der eindeutig ist, erscheint keine bessere Alternative zu haben, und ist in einer einigermaßen renommierten Quelle verwendet wird , auch wenn es nicht viel verbreitet hat. Tatsächlich würde ich sagen, dass die Tatsache, dass sie sich trotz einer extrem häufigen Komplexitätsklasse nicht verbreitet hat, darauf hindeutet, dass es an der Zeit ist, dass die Leute mehr damit anfangen!
links um den
+1 "nur weit verbreiteter Name für diese Funktion ist n log n" - Alle anderen Antworten sind unterhaltsam und erbaulich, aber ich denke, Sie haben vielleicht Recht. Ich übe seit ein paar Tagen, "linearithmisch" zu sagen und es rollt immer noch nicht von der Zunge. "En log en" ist leicht zu sagen, leicht zu merken und wird von jedem, der mit Big O vertraut ist, sofort verstanden. Ich werde ein wenig darüber nachdenken, aber möglicherweise muss ich meine Akzeptanz auf diese Antwort verlagern.
GlenPeterson