Qual é o nome da classe de funções descrita por O (n log n)?

40

Em "Big O", notações comuns têm nomes comuns (em vez de dizer "Oh, de algum fator constante"):

O (1) é "Constante"

O (log n) é "logarítmico"

O (n) é "Linear"

O (n ^ 2) é "Quadrático"

O (n * log n) é ???

É apenas "n log n" ou tem um nome especial como o acima?

terminology asymptotics GlenPeterson
fonte
4
Duplicação entre sites para referência: ao falar, como posso dizer que a ordem da complexidade de tempo de um algoritmo é O (N log N)?
Philip Kendall

Respostas:

52

É chamado tempo linearitmico e é um caso especial de uma classe mais geral conhecida como quase linear . Como o nome sugere, os algoritmos que se enquadram nessa classe quase rodam em tempo linear; na verdade, eles têm uma complexidade menor que os algoritmos que são executados em com k > 1 .O(nk)k>1

Roukah
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Gilles 'SO- stop be evil'
17

linearitmico: adj.

De um algoritmo, com tempo de execução que é O (N log N). Cunhado como um portmanteau de 'linear' e 'logarítmico' em Algoritmos em C por Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7).

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

miracle173
fonte
Por que não estou surpreso que ele vem de carriço ... :)
TextGeek
11

Eu sempre ouvi O (n log n) descrito como "log-linear", o que me parece correto.

Dylan Skola
fonte
4
Dito isto, uma referência ou duas seria legal.
Raphael
7

Isso foi muito longo para um comentário, então escrevi uma resposta. Não adicionei isso à minha primeira resposta porque muitas pessoas já votaram positivamente no meu primeiro vanswer e não tenho certeza de que elas também concordam com essa resposta.

  • Eu não acho que linearitmico seja um termo bem estabelecido, como declarado em um comentário à resposta aceita. Pesquisei alguns artigos bastante jovens usando esse termo, um curso de ciências da computação e outro livro de Sedgewick que usa esse termo e muitos dicionários on-line.
  • O termo quaseilinear eu encontrei em dois artigos:

    A satisfação é quase completa no NQL
    CP Schnorr
    Journal da Association for Computing Machinery,
    Vol. 25, nº 1, janeiro de 1978, pp 136-1,15

e em um artigo citado na Wikipedia que lida com o artigo de Schorr. Schnorr apresenta as classes de complexidade quasilinear (QL) e não-determinística quasilinear (NQL).
Quase-linear também parece ser usado na teoria de equações diferenciais parciais.

Em suma, parece que um ou mais wikipedistas queriam fornecer nomes para essa função que não tem um nome amplamente aceito. Mas, mesmo agora, parece-me que nenhum dos nomes é amplamente aceito (além disso, acho que esse é um tipo de manipulação que a Wikipedia não deve fazer). Acho que é preciso ter cuidado se usar a Wikipedia para questões de terminologia. E para esta função não é uma fonte suficiente. Eu acho que o único nome amplamente aceito para essa função é n log n .

miracle173
fonte
11
Enquanto a legitimidade de linearithmic e loglinear pode ser discutível, acredito que quasi-linear é um termo bem estabelecida. Parece ser amplamente utilizado em trabalhos de pesquisa.
Roukah
@Roukah sim, mas isso não significa exatamente a mesma coisa; quaseilinear é mais geral. - Não vejo o que há de errado com a Wikipedia usando um nome inequívoco, parece não ter alternativa melhor e é usado em uma fonte razoavelmente renomada, mesmo que não tenha se espalhado muito. Na verdade, eu diria que o fato de não ter se espalhado, apesar de ser uma classe de complexidade extremamente comum, sugere que é hora de as pessoas começarem a usá-lo mais!
leftaroundabout
+1 "o único nome amplamente aceito para esta função é n log n" - Todas as outras respostas são divertidas e edificantes, mas acho que você pode estar certo. Eu pratico dizendo "linearitmico" há alguns dias e ainda não sai da língua. "En log en" é fácil de dizer, fácil de lembrar e instantaneamente entendido por todos os familiarizados com o Big O. Pensarei um pouco sobre isso, mas talvez precise mudar minha aceitação para esta resposta.
GlenPeterson