¿Cuál es el nombre de la clase de funciones descritas por O (n log n)?

Respuestas:

52

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(nortek)k>1

Roukah
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Gilles 'SO- deja de ser malvado'
17

linearithmic: adj.

De un algoritmo, que tiene un tiempo de ejecución que es O (N log N). Acuñado como un acrónimo de 'lineal' y 'logarítmico' en Algorithms In C por Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7).

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

milagro173
fuente
¿Por qué no me sorprende que provenga de Sedge ... :)
TextGeek
11

Siempre he escuchado a O (n log n) descrito como "log-linear", lo que me parece correcto.

Dylan Skola
fuente
44
Dicho esto, una referencia o dos sería bueno.
Raphael
7

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.

  • No creo que linearithmic sea ​​un término bien establecido como se indica en un comentario a la respuesta aceptada. Busqué en Google algunos artículos bastante jóvenes usando este término, un curso de CS y otro libro de Sedgewick que usa este término y muchos diccionarios en línea.
  • El término cuasilineal que encontré en dos artículos:

    La satisfacción es casi completa en NQL
    CP Schnorr
    Journal of the Association for Computing Machinery,
    Vol 25. No 1, enero de 1978, pp 136-1,15

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 .

milagro173
fuente
1
Si bien la legitimidad de linearithmic y loglinear podría ser discutible, creo que cuasi-linear es un término bien establecido. Parece ser ampliamente utilizado en trabajos de investigación.
Roukah
@ Rukah sí, pero no significa exactamente lo mismo; cuasilineal es más general. - No veo qué hay de malo en que Wikipedia use un nombre que no sea ambiguo, que no parezca tener una mejor alternativa y que se use en una fuente razonablemente reconocida, incluso si no se ha extendido mucho. De hecho, diría que el hecho de que no se haya extendido a pesar de ser una clase de complejidad extremadamente común sugiere que ¡ya es hora de que la gente empiece a usarlo más!
Leftaroundabout
+1 "el único nombre ampliamente aceptado para esta función es n log n" - Todas las otras respuestas son entretenidas y edificantes, pero creo que puede tener razón. He estado practicando decir "linearithmic" durante un par de días y todavía no sale de la lengua. "En log en" es fácil de decir, fácil de recordar e instantáneamente entendido por todos los que están familiarizados con Big O. Lo pensaré un poco, pero podría tener que cambiar mi aceptación a esta respuesta.
GlenPeterson