Existe-t-il un terme abrégé pour O (n log n)?

Nous avons généralement un seul mot pour la plupart des complexités que nous rencontrons dans l'analyse algorithmique:Existe-t-il un terme abrégé pour O (n log n)?

O(1) == "constante"
O(log n) == "logarithmique"
O(n) == "linéaire"
O(n^2) == "quadratique"
O(n^3) == "cube"
O(2^n) == « exponentielle "

Nous rencontrons des algorithmes avec O(n log n) complexité avec une certaine régularité (pensez à tous les algorithmes dominés par la complexité de tri) mais pour autant que je sache, il n'y a pas un seul mot, nous pouvons utiliser en anglais pour se référer à cette complexité. Est-ce une lacune dans ma connaissance, ou une réelle lacune dans notre discours anglais sur la complexité computationnelle?

Source

2010-04-14 jemfinch

Pour tous answerers Prenant note du nombre de syllabes, ce n'est pas sur l'optimisation (je vous induits en erreur avec mon utilisation de « raccourci » ci-dessus), mais plus de parler couramment (à savoir, coulant, contrairement à cette digression entre parenthèses) anglais. – jemfinch

Peut-être en utilisant le terme commun "nlogn" qui a peu ou pas d'autres significations - est couramment, anglais commun. –

@Joe: Peut-être pas l'anglais commun, mais tout le monde discutant de la complexité algorithmique devrait être capable de l'utiliser couramment. –

O(n log n) == "linearithmic"

semble avoir été inventé par Robert Sedgewick dans le livre Algorithmes Dans C. Aussi appelé quasi-linéaire ou log-linéaire. Cependant, linearithmic a le bonus supplémentaire de ne pas être un terme surchargé (quasilinéaire est utilisé en économie et équations différentielles, alors que logminear est utilisé en économie et en analyse de régression).

Source

2010-04-14 17:08:47

D'après les regards des autres réponses, je ne pense pas que ce soit un langage courant (je n'en avais jamais entendu parler), donc par souci de clarté je resterais avec "inlogin" ou vous pourriez avoir des regards étranges. +1 cependant - peut-être dans le temps cela deviendra un terme banal (bizarre que ce n'est pas déjà fait). –

Je suspecte le "matériel original" sur cette entrée. ... "Résultats 1 - 10 sur environ 1 080 pour linearithmic." google.com/search?q=linearithmic –

Je reçois 9600 hits pour cette recherche. – Nitrodist

"en log en" a moins de syllabes que "exponentielle" ou "logarithmique". Je pense que la plupart des gens disent cela.

Source

2010-04-14 17:07:01

Aussi, pourquoi est-ce que "double-vous double-vous double-vous" (9 syllabes) sténographie pour "world wide web" (3 syllabes) ??? –

Ceci est vrai, mais linéaire est plus long que «n» et les gens le disent. –

@Joe - peut-être c'est pourquoi beaucoup de gens disent juste "dub-dub-dub."Pas moi, bien sûr, je pense que ça vous donne l'air d'un idiot qui bafouille – tvanfosson

Je ne crois pas qu'il existe un tel terme. Plus pertinent, cependant, est cette pensée: Pourquoi faites-vous référence à exponentiel (11 caractères) comme un "raccourci" pour O (2^n) (6 caractères)?

Personnellement, je suis très heureux de dire que "cet algorithme s'exécute en log temps". C'est tout ce que la plupart des gens ont besoin d'entendre.

Source

2010-04-14 17:08:05

Maintenant, disons que "cet algorithme s'exécute en deux à l'instant" contre "cet algorithme fonctionne en temps exponentiel". ce dernier est, à mon avis, plus idiomatique et plus facile à dire –

Oui, je suis d'accord avec vous là-bas. Je n'ai jamais prétendu que l'exponentielle n'était pas plus facile à dire. Mais je ne crois pas qu'il existe une manière simple et idiomatique d'exprimer le produit d'une fonction de croissance linéaire et logarithmique. –

-1

Il n'y a pas de mot équivalent pour O (nlogn). Il vous suffit de passer le temps supplémentaire en disant la chose (Remarque: même nombre de syllabes comme « exponentielle »)

Source

2010-04-14 17:08:05 chetan

Selon Wikipedia vous pouvez l'appeler linearithmic, loglinear ou quasilinéaire.

Source

2010-04-14 17:09:03

Parmi ces trois, seul loglinear est quelque peu clair dans ce que cela signifie. Bien que les deux autres semblent certainement un peu cool. –

"Résultats 1 - 10 sur environ 1 080 pour linearithmic." http://www.google.com/search?q=linearithmic –

Je préfère «loglinear» moi-même. Il y a aussi la variante [logilinear] (http://www.google.com/search?q=logilinear) dans la nature, mais ceci n'est officiellement reconnu par aucun dictionnaire, et ne semble être utilisé que dans le contexte de loglinear la modélisation. –

O(2^n) == « O Effrayant »

Source

2010-04-14 17:09:49 JensenDied

Ou peut-être "O merde"? :) – jemfinch

Existe-t-il un terme abrégé pour O (n log n)?

Répondre

Questions connexes