Ao falar, como posso dizer que a ordem da complexidade temporal de um algoritmo é O (N log N)?

22

Que termo posso usar para descrever algo com complexidade O (N log N)?

Por exemplo:

  • O (1): Constante

  • O (log N): logarítmico

  • O (N): Linear

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

  • O (N 2 ): Quadrático

  • O (N 3 ): Cúbico

algorithms algorithm-analysis big-o matiascelasco
fonte
5
Costumo aqui o termo amplo "quase-linear" para significar O(n · f(n))onde f(n) << n. Mas isso também combina com coisas como O(n · log log n)e O(n α(n))onde α(n)é o inverso da função Ackermann.
Bakuriu 18/07/2015
en.wikipedia.org/wiki/…
Ry-
34
"Oh enn log enn" provavelmente é bom o suficiente.
user253751
Duplicação entre sites aqui: qual é o nome da classe de funções descrita por O (n log n)?
martin

Respostas:

60

"N log N" é tão bom quanto você conseguirá e deve ser bem compreendido por programadores profissionais. Você não pode esperar que exista uma única palavra para descrever todas as classes de complexidade que existem.

Philip Kendall
fonte
6
“Não podemos esperar que exista uma única palavra para descrever todas as classes de complexidade” - certamente não. Mas n ( n ⋅ log n ) é uma classe tão importante que merece um nome próprio, IMO; e como dito por Steve Jessop, o linearitmico já é bastante comum.
leftaroundabout
@leftaroundabout É de fato bastante comum que você possa argumentar, que merece um nome. Mas "n log n" é curto o suficiente para pronunciar (apenas três sílabas) que funciona bem como um nome. Para comparação, "Logarítmico" são quatro sílabas. É mais interessante quando você acessa algoritmos externos, onde a maioria dos algoritmos "n log n" obtém complexidade $ N log_B (N / B) $, que certamente seria uma classe de complexidade digna de um nome mais curto.
kasperd
10
Como estudante de mestrado em ciência da computação, ouvi "enn log enn" ao longo dos meus estudos universitários. Eu nunca ouvi "linearitmico" e não entenderia o que isso significava a princípio.
Kevin - Restabelece Monica
@ Kevin: Logarítmico é quatro sílabas, mas "log-enn" é apenas duas. Da mesma forma, O (N ^ 2) é "enn ao quadrado", não "quadrático". Suponho que "cúbico" tenha menos fonemas do que "enn-cubed", mas acho que o último termo ainda seria mais comum.
Supercat 26/07
51

Existe um termo de jargão linearitmico que significa exatamente isso.

Não acredito que seja universalmente entendido por todos os programadores; portanto, se você não tomar cuidado, ele obscurecerá mais do que informa. Pessoalmente, normalmente não o uso e, se o fizesse, provavelmente o definiria no primeiro uso, por exemplo "este artigo considera O(N log N)algoritmos linearitmicos ( )".

Steve Jessop
fonte
11
Nunca soube que existia!
David diz Reinstate Monica
12

Às vezes é chamado de "loglinear", embora essa palavra realmente signifique algo diferente. Gostaria apenas de "N log N", como sugere a resposta de Philip .

Jörg W Mittag
fonte
1
Qual é o significado alternativo para log-linear? Se eu quisesse um nome diferente de 'N log N', log-linear é o termo que eu usaria.
22815 Jonathan
2
@JonathanLeffler: Eu assumo en.wikipedia.org/wiki/Log-linear_analysis às vezes seja escrito sem o hífen. É claro que, com espaço para nome adequado, você poderia usar a mesma palavra para uma classe de complexidade.
18715 Steve Steveop
@SteveJessop: Certamente foi o que surgiu através de uma pesquisa no Google. Não tenho certeza se estou disposto a aceitar a combinação Google / Wikipedia como autorizada, embora não tenha dúvidas de que a análise log-linear é a descrita.
27616 Jonathan
1
@ JonathanLeffler: também pode significar o que eu chamaria de um gráfico de log-lin ou log-lin (ou, porque sou preguiçoso, na verdade eu costumava chamá-los de gráfico de log como diferente de um log-log). Talvez possamos perguntar: qual significado alternativo esta resposta tem em mente :-)
Steve Jessop
2

Como o fator log ncresce lentamente, uma descrição qualitativa para " O(n log n)seria quase linear". Dependendo do seu público, a classe de O(n log n)algoritmos pode ser bem conhecida, como por exemplo, este é o caso da classificação rápida de nitens por comparação.

hardmath
fonte