Gibt es eine Kurzbezeichnung für O (n log n)?

Wir haben in der Regel nur ein einziges Wort für die meisten komplex wir in algorithmischer Analyse auftreten:Gibt es eine Kurzbezeichnung für O (n log n)?

O(1) == "Konstante"
O(log n) == "logarithmische"
O(n) == "linear"
O(n^2) == "quadratisch"
O(n^3) == "cubic"
O(2^n) == „exponentiell "

Wir begegnen Algorithmen mit O(n log n) Komplexität mit einer gewissen Regelmäßigkeit (man denke an alle von Art Komplexität beherrscht Algorithmen), aber soweit ich weiß, gibt es kein einziges Wort, das wir in Englisch verwenden können, um diese Komplexität zu verweisen. Ist das eine Lücke in meinem Wissen oder eine wirkliche Lücke in unserem englischen Diskurs über Rechenkomplexität?

Quelle

2010-04-14 jemfinch

An allen Beantwortern die Anzahl der Silben unter Hinweis darauf, dies nicht über die Optimierung ist (ich verleitet Sie mit meiner Verwendung von „Kurzschrift“ oben), aber mehr über fließend sprechen (dh fließend, viel anders als diese Abschweifung in Klammern. – jemfinch

Vielleicht ist die gebräuchliche Bezeichnung "nlogn", die wenige, wenn auch keine anderen Bedeutungen hat, fließend, allgemeines Englisch. –

@Joe: Vielleicht nicht allgemeines Englisch, aber jeder, der algorithmische Komplexität diskutiert, sollte es fließend benutzen können. –

O(n log n) == "linearithmic"

scheint von Robert Sedgewick in die geprägt wurden Buch Algorithmen in C. Auch als quasilinear oder loglinear bezeichnet. Jedoch hat Linearithmisch den zusätzlichen Vorteil, dass es kein überladener Term ist (quasilinear wird in der Ökonomie und Differentialgleichungen verwendet, während loglinear in der Ökonomie und Regressionsanalyse verwendet wird).

Quelle

2010-04-14 17:08:47

Aus dem Blick der anderen Antworten, ich denke nicht, dass dies der übliche Sprachgebrauch ist (ich hatte noch nie davon gehört), also würde ich aus Gründen der Klarheit bei "inlogin" bleiben oder du könntest ein paar komische Blicke bekommen. +1 - vielleicht in der Zeit wird dies ein alltäglicher Begriff (seltsam, dass es nicht schon ist). –

Ich vermute "Original-Material" auf diesem Eintrag. ... "Ergebnisse 1 - 10 von etwa 1.080 für linearithmische." google.com/search?q=linearithmic –

Ich bekomme 9600 Treffer für diese Suche. – Nitrodist

"en log en" hat weniger Silben als "exponentiell" oder "logarithmisch". Ich denke, die meisten Leute sagen das einfach.

Quelle

2010-04-14 17:07:01

Auch, warum ist "double-you double-you double-you" (9 Silben) Kurzschrift für "world wide web" (3 Silben) ??? –

Das ist wahr, aber linear ist länger als 'n' und die Leute sagen das. –

@Joe - vielleicht deshalb sagen viele Leute einfach "Dub-Dub-Dub."Nicht ich, natürlich, ich denke, das macht dich wie ein blabbernder Idiot klingen. – tvanfosson

Ich glaube nicht, dass es einen solchen Begriff gibt.

Relevanter ist dieser Gedanke: Warum bezeichnen Sie Exponential (11 Zeichen) als "Kurzschrift" für O (2^n) (6 Zeichen)?

Persönlich bin ich ziemlich glücklich zu sagen "dieser Algorithmus läuft en log en Zeit". Es ist alles, was die meisten Leute hören müssen.

Quelle

2010-04-14 17:08:05

Sagen Sie jetzt "dieser Algorithmus läuft in zwei zur Enthzeit" versus "dieser Algorithmus läuft in der exponentiellen Zeit" Letzteres ist meiner Meinung nach idiomatischer und leichter zu sagen. –

Ja, da stimme ich dir zu. Ich behauptete nie, dass Exponential nicht einfach zu sagen war. Aber ich glaube nicht, dass es eine einfache, idiomatische Art gibt, das Produkt einer linearen und logarithmischen Wachstumsfunktion auszudrücken. –

-1

Nein, es gibt kein einheitliches Wort für O (nlogn). Sie müssen nur die zusätzliche Zeit verbringen, die ganze Sache zu sagen (Hinweis: gleiche Anzahl von Silben wie „exponentiell“)

Quelle

2010-04-14 17:08:05 chetan

Nach Wikipedia können Sie nennen es linearithmic, loglinearen oder quasilineare.

Quelle

2010-04-14 17:09:03

Von diesen drei ist nur loglinear etwas klar, was es bedeutet. Die anderen beiden klingen allerdings irgendwie cool. –

"Ergebnisse 1 - 10 von etwa 1.080 für linearithmische." http://www.google.com/search?q=linearithmic –

Ich bevorzuge 'loglinear' selbst. Es gibt auch die Variante [logilinear] (http://www.google.com/search?q=logilinear) in der freien Wildbahn, aber dies wird von keinem Wörterbuch offiziell anerkannt und scheint nur im Kontext von loglinear verwendet zu werden Modellieren. –

O(2^n) == „O Scary“

Quelle

2010-04-14 17:09:49 JensenDied

Oder vielleicht "O Scheiße"? :) – jemfinch

Gibt es eine Kurzbezeichnung für O (n log n)?

Antwort

Verwandte Themen