En parlant, comment puis-je dire que l'ordre de complexité temporelle d'un algorithme est O (N log N)?

22

Quel terme puis-je utiliser pour décrire quelque chose avec une complexité O (N log N)?

Par exemple:

  • O (1): Constante

  • O (log N): Logarithmique

  • O (N): linéaire

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

  • O (N 2 ): Quadratique

  • O (N 3 ): Cubique

algorithms algorithm-analysis big-o matiascelasco
la source
5
J'ai souvent ici le terme large "quasi-linéaire" pour signifier O(n · f(n))où f(n) << n. Mais cela correspond aussi à des choses comme O(n · log log n)et O(n α(n))où α(n)est l'inverse de la fonction Ackermann.
Bakuriu
en.wikipedia.org/wiki/…
Ry-
34
"Oh enn log enn" est probablement suffisant.
user253751
Cross-site duplicate here: Quel est le nom de la classe de fonctions décrite par O (n log n)?
martin

Réponses:

60

"N log N" est aussi bon que vous allez en avoir, et devrait être bien compris par les programmeurs professionnels. Vous ne pouvez pas vous attendre à ce qu'il y ait un seul mot pour décrire chaque classe de complexité qui existe.

Philip Kendall
la source
6
«Ne peut pas s'attendre à ce qu'il y ait un seul mot pour décrire chaque classe de complexité» - certainement pas. Mais 𝓞 ( n ⋅ log n ) est une classe tellement importante qu'elle mérite bien son nom, IMO; et comme l'a dit Steve Jessop, la linéarité est déjà assez courante.
leftaroundabout
@leftaroundabout Il est en effet assez courant que vous puissiez affirmer qu'il mérite un nom. Mais "n log n" est assez court pour prononcer (seulement trois syllabes) qu'il fonctionne bien comme nom. A titre de comparaison, «logarithmique» est composé de quatre syllabes. C'est plus intéressant lorsque vous arrivez à des algorithmes externes où la plupart des algorithmes "n log n" obtiennent la complexité $ N log_B (N / B) $, ce serait certainement une classe de complexité digne d'un nom plus court.
kasperd
10
En tant qu'étudiant de maîtrise en informatique, j'ai entendu "enn log enn" tout au long de mes études collégiales. Je n'ai jamais entendu parler de «linéarité» et je ne comprendrais pas ce que cela signifiait au début.
Kevin - Réintègre Monica le
@Kevin: Logarithmic est quatre syllabes, mais "log-enn" n'est que deux. De même, O (N ^ 2) est "enn-carré", pas "quadratique". Je suppose que "cubic" a moins de phonèmes que "enn-cubed", mais je pense que ce dernier terme serait encore plus courant.
supercat
51

Il existe un terme de jargon linéarithmique qui signifie exactement cela.

Je ne pense pas que ce soit universellement compris par tous les programmeurs, donc si vous ne faites pas attention, cela obscurcira plus qu'il n'informe. Personnellement, je ne l'utilise pas normalement, et si je le faisais, je le définirais probablement lors de la première utilisation, par exemple "cet article considère les O(N log N)algorithmes linearithmic ( )".

Steve Jessop
la source
11
Je n'ai même jamais su que ça existait!
David dit de rétablir Monica le
12

Il est parfois appelé "loglinear", bien que ce mot signifie en réalité quelque chose de différent. Cependant, je me contenterais de "N log N", comme le suggère la réponse de @ Philip .

Jörg W Mittag
la source
1
Quelle est la signification alternative de log-linéaire? Si je voulais un nom autre que «N log N», log-linear est le terme que j'utiliserais.
Jonathan Leffler
2
@JonathanLeffler: Je suppose que en.wikipedia.org/wiki/Log-linear_analysis s'écrit parfois sans le trait d'union. Bien sûr, avec un espace de noms approprié, vous pourriez avec plaisir utiliser le même mot pour une classe de complexité.
Steve Jessop
@SteveJessop: C'est certainement ce qui est ressorti d'une recherche Google. Je ne sais pas si je suis prêt à accepter le combo Google / Wikipedia comme faisant autorité, bien que je ne doute aucunement que l'analyse log-linéaire est telle que décrite.
Jonathan Leffler
1
@JonathanLeffler: pourrait également signifier ce que j'appellerais un tracé de log-log ou de log-lin (ou, parce que je suis paresseux, en fait je les appellerais souvent un plot de log par opposition à un log-log). Nous pourrions peut-être nous demander quelle alternative signifie cette réponse:
Steve Jessop
2

Parce que le facteur log ncroît lentement, une description qualitative de O(n log n)serait «presque linéaire». Selon votre public, la classe d' O(n log n)algorithmes peut être bien connue, comme c'est le cas par exemple pour le tri rapide des néléments par comparaison.

hardmath
la source