Quel est le nom de la classe de fonctions décrite par O (n log n)?

40

Dans "Big O", les notations communes ont des noms communs (au lieu de dire "Oh comme facteur constant"):

O (1) est "constante"

O (log n) est "logarithmique"

O (n) est "linéaire"

O (n ^ 2) est "quadratique"

O (n * log n) est ???

Est-ce juste "n log n" ou est-ce qu'il a un nom spécial comme ci-dessus?

terminology asymptotics GlenPeterson
la source
4
Copie inter-site à titre de référence: en parlant, comment dire que l'ordre de complexité temporelle d'un algorithme est O (N log N)?
Philip Kendall

Réponses:

52

C'est ce qu'on appelle le temps linéarithmique , et il s'agit d'un cas particulier d'une classe plus générale appelée quasi linéaire . Comme son nom l'indique, les algorithmes de cette classe fonctionnent presque en temps linéaire; en fait, ils ont une complexité inférieure à celle des algorithmes qui fonctionnent en avecO(nk) .k>1

Roukah
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Gilles 'SO- arrête d'être méchant'
17

linearithmique: adj.

D'un algorithme ayant un temps d'exécution égal à O (N log N). Monnayé comme un baguette de «linéaire» et «logarithmique» dans Algorithms In C de Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7).

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

miracle173
la source
Pourquoi ne suis-je pas surpris que cela vienne de Sedge ... :)
TextGeek Le
11

J'ai toujours entendu O (n log n) décrit comme "log-linéaire", ce qui me semble à peu près correct.

Dylan Skola
la source
4
Cela dit, une référence ou deux serait bien.
Raphaël
7

C'était trop long pour un commentaire, alors j'ai écrit une réponse. Je n’ai pas ajouté cela à ma première réponse car beaucoup de personnes ont déjà voté pour mon premier représentant et je ne suis pas sûr qu’elles soient d’accord avec cette réponse également.

  • Je ne pense pas que linearithmic soit un terme bien établi, comme indiqué dans un commentaire sur la réponse acceptée. J'ai cherché sur Google des articles assez jeunes utilisant ce terme, un cours CS et un autre livre de Sedgewick qui utilise ce terme et de nombreux dictionnaires en ligne.
  • Le terme quasilinéaire que j'ai trouvé dans deux articles:

    La satisfaction est quasilinéaire complète dans NQL
    CP Schnorr
    Journal de l’Association for Computing Machinery,
    vol 25. No 1, janvier 1978, p. 136-1,15

et dans un article cité dans Wikipedia qui traite de cet article de Schorr. Schnorr introduit les classes de complexité quasi-linéaires (QL) et quasi-linéaires non déterministes (NQL).
Quasilinear semble également être utilisé dans la théorie des équations aux dérivées partielles.

Dans l’ensemble, il semble qu’un ou plusieurs wikipédiens aient voulu fournir des noms pour cette fonction qui n’ont pas de nom largement accepté. Mais même maintenant, il me semble qu'aucun des noms n'est largement accepté (à part cela, je pense que c'est une sorte de manipulation que Wikipedia ne devrait pas faire). Je pense qu'il faut être prudent si l'on utilise Wikipedia pour des questions de terminologie. Et pour cette fonction, ce n'est pas une source suffisante. Je pense que le seul nom largement accepté pour cette fonction est n log n .

miracle173
la source
1
Bien que la légitimité de linéarithmique et log -linéaire puisse être discutée, je pense que quasi-linéaire est un terme bien établi. Il semble être largement utilisé dans les documents de recherche.
Roukah
@Roukah oui, mais cela ne veut pas dire la même chose; quasi-linéaire est plus général. - Je ne vois pas ce qui ne va pas avec Wikipedia qui utilise un nom non ambigu, qui ne semble pas avoir de meilleure alternative et qui est utilisé dans une source raisonnablement renommée, même si elle ne s'est pas beaucoup répandue. En fait, je dirais que le fait qu'il ne se soit pas répandu malgré le fait qu'il s'agisse d'un cours de complexité extrêmement courant suggère qu'il est grand temps que les gens l'utilisent davantage!
gauche du
+1 "seul nom largement accepté pour cette fonction est n log n" - Toutes les autres réponses sont divertissantes et édifiantes, mais je pense que vous avez peut-être raison. Je m'entraîne à dire "linearithmic" depuis quelques jours maintenant et ça ne roule toujours pas. "En log fr" est facile à dire, facile à retenir, et compréhensible instantanément par tous ceux qui sont familiers avec Big O. Je vais y réfléchir un peu, mais je devrai peut-être accepter plus facilement cette réponse.
GlenPeterson