Al hablar, ¿cómo puedo decir que el orden de complejidad temporal de un algoritmo es O (N log N)?

22

¿Qué término puedo usar para describir algo con complejidad O (N log N)?

Por ejemplo:

  • O (1): constante

  • O (log N): logarítmico

  • O (N): lineal

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

  • O (N 2 ): Cuadrático

  • O (N 3 ): cúbico

algorithms algorithm-analysis big-o matiascelasco
fuente
55
A menudo aquí el término amplio "cuasi-lineal" significa O(n · f(n))dónde f(n) << n. Pero esto también coincide con cosas como O(n · log log n)y O(n α(n))dónde α(n)es la inversa de la función de Ackermann.
Bakuriu
en.wikipedia.org/wiki/…
Ry-
34
"Oh enn log enn" es probablemente lo suficientemente bueno.
user253751
Cross-site duplicate here: ¿Cuál es el nombre de la clase de funciones descritas por O (n log n)?
Martin

Respuestas:

60

"N log N" es tan bueno como lo que vas a obtener, y los programadores profesionales deben entenderlo bien. No puede esperar que haya una sola palabra para describir cada clase de complejidad que existe.

Philip Kendall
fuente
66
"No puedo esperar que haya una sola palabra para describir cada clase de complejidad", ciertamente no. Pero 𝓞 ( n ⋅ log n ) es una clase tan importante que merece un nombre propio, IMO; y como dijo Steve Jessop, linearithmic ya es bastante común.
Leftaroundabout
@leftaroundabout De hecho, es bastante común que puedas argumentar que merece un nombre. Pero "n log n" es lo suficientemente corto como para pronunciar (solo tres sílabas) que funciona bien como nombre. A modo de comparación, "logarítmico" son cuatro sílabas. Es más interesante cuando se llega a algoritmos externos donde la mayoría de los algoritmos "n log n" obtienen complejidad $ N log_B (N / B) $, que sin duda sería una clase de complejidad digna de un nombre más corto.
kasperd
10
Como estudiante de maestría en ciencias de la computación, he escuchado "enn log enn" durante mis estudios universitarios. Nunca he escuchado "linearithmic" y no entendería lo que significaba al principio.
Kevin - Restablece a Mónica el
@Kevin: Logarithmic son cuatro sílabas, pero "log-enn" es solo dos. Del mismo modo, O (N ^ 2) es "enn-cuadrado", no "cuadrático". Supongo que "cúbico" tiene menos fonemas que "enn-cubed", pero creo que el último término aún sería más común.
supercat
51

Hay un término jerárquico linearithmic que significa exactamente esto.

No creo que todos los programadores lo entiendan universalmente, así que si no tienes cuidado, oscurecerá más de lo que informa. Personalmente, normalmente no lo uso, y si lo hiciera, probablemente lo definiría en el primer uso, por ejemplo, "este artículo considera los O(N log N)algoritmos linearithmic ( )".

Steve Jessop
fuente
11
¡Ni siquiera sabía que existía!
David dice reinstalar a Mónica el
12

A veces se le llama "loglinear", aunque esa palabra en realidad significa algo diferente. Sin embargo, me quedaría con "N log N", como sugiere la respuesta de @ Philip .

Jörg W Mittag
fuente
1
¿Cuál es el significado alternativo para log-linear? Si quisiera un nombre que no sea 'N log N', log-linear es el término que usaría.
Jonathan Leffler
2
@ JonathanLeffler: Supongo que en.wikipedia.org/wiki/Log-linear_analysis a veces se escribe sin el guión. Por supuesto, con un espacio de nombres adecuado, podría usar la misma palabra para una clase de complejidad.
Steve Jessop
@SteveJessop: Eso es ciertamente lo que surgió a través de una búsqueda en Google. No estoy seguro de si estoy dispuesto a aceptar el combo Google / Wikipedia como autorizado, aunque no tengo ninguna duda de que el análisis log-lineal es como se describe.
Jonathan Leffler
1
@JonathanLeffler: también podría significar lo que yo llamaría un gráfico de lin-log o log-lin (o, debido a que soy flojo, en realidad a menudo los llamaría un gráfico de log a diferencia de uno de log-log). Quizás podríamos preguntar, qué significado alternativo tiene en mente esta respuesta :-)
Steve Jessop
2

Debido a que el factor log ncrece lentamente, una descripción cualitativa para O(n log n)sería "casi lineal". Dependiendo de su audiencia, la clase de O(n log n)algoritmos puede ser bien conocida, como por ejemplo este es el caso de la clasificación rápida de nelementos por comparación.

hardmath
fuente