En "Big O", las anotaciones comunes tienen nombres comunes (en lugar de decir, "Oh, de algún factor constante"):
O (1) es "constante"
O (log n) es "Logarítmico"
O (n) es "Lineal"
O (n ^ 2) es "Cuadrático"
O (n * log n) es ???
¿Es solo "n log n" o tiene un nombre especial como el anterior?
terminology
asymptotics
GlenPeterson
fuente
fuente
Respuestas:
Se llama tiempo linealitmico , y es un caso especial de una clase mas general conocida como cuasi lineal . Como su nombre indica, los algoritmos que se incluyen en esta clase casi se ejecutan en tiempo lineal; de hecho tienen una complejidad menor que los algoritmos que se ejecutan en con k > 1 .O ( nk) k > 1
fuente
http://catb.org/jargon/html/L/linearithmic.html
fuente
Siempre he escuchado a O (n log n) descrito como "log-linear", lo que me parece correcto.
fuente
Esto fue demasiado largo para un comentario, así que escribí una respuesta. No agregué esto a mi primera respuesta porque muchas personas ya votaron por mi primera respuesta y no estoy seguro de que también estén de acuerdo con esta respuesta.
y en un artículo citado en Wikipedia que trata el artículo de este Schorr. Schnorr presenta las clases de complejidad cuasilineales (QL) y no deterministas cuasilineales (NQL).
Quasilineal parece ser utilizado en la teoría de ecuaciones diferenciales parciales, también.
En general, parece que uno o más Wikipedians querían proporcionar nombres para esta función que no tiene un nombre ampliamente aceptado. Pero incluso ahora me parece que ninguno de los nombres es ampliamente aceptado (además de eso, creo que este es un tipo de manipulación que Wikipedia no debería hacer). Creo que hay que tener cuidado si se usa Wikipedia para preguntas de terminología. Y para esta función no es una fuente suficiente. Creo que el único nombre ampliamente aceptado para esta función es n log n .
fuente