O (N log N) Complejidad - Similar a lineal?

Question

Así que creo que voy a ser enterrados por hacer una pregunta tan trivial pero estoy un poco confundido acerca de algo.

He implementado clasificación rápida en Java y C y estaba haciendo algunas comparissons básicos. El gráfico salió como dos líneas rectas, con la C es de 4 ms más rápido que la contraparte de Java más de 100.000 enteros aleatorios.

El código para mis pruebas se puede encontrar aquí;

android-puntos de referencia

No estaba segura de lo que es un (n log n) la línea se vería, pero no pensé que sería recta. Sólo quería comprobar que esto es el resultado esperado y que no debería tratar de encontrar un error en mi código.

Me pegué la fórmula en Excel y para la base 10 que parece ser una línea recta con una torcedura en el inicio. Es esto debido a la diferencia entre log (n) y log (n + 1) aumenta linealmente?

Gracias,

Gav

Answer 1

hacer que el gráfico más grande y verá que O (n log n) no es exactamente una línea recta. Pero sí, es bastante cerca a un comportamiento lineal. Para ver por qué, sólo toma el logaritmo de un par de números muy grandes.

Por ejemplo (base 10):

log(1000000) = 6
log(1000000000) = 9
…

Por lo tanto, para ordenar los números 1.000.000, un O (n) logn clasificación añade un factor despreciable 6 (o simplemente un poco más ya que la mayoría de los algoritmos de ordenación dependerán de la base 2 logaritmos). No es una gran cantidad.

De hecho, este factor de registro es so extraordinariamente pequeña que para la mayoría de órdenes de magnitud, O establecido (n log n) algoritmos superan a los algoritmos de tiempo lineal. Un ejemplo destacado es la creación de una estructura de datos de sufijos matriz.

Un simple caso ha mordido recientemente me cuando trataba de mejorar una clasificación rápida clasificación de cadenas cortas mediante el empleo de radix especie. Resulta que, para las cadenas cortas, esto (tiempo lineal) Radix sort era más rápido que la clasificación rápida, pero hubo un punto de inflexión para las cadenas relativamente cortas, ya raíz depende fundamentalmente de la especie longitud de las cuerdas a clasificar.

Answer 2

FYI, quicksort es en realidad O (n ^ 2), pero con un caso promedio de O (nlogn)

FYI, hay una diferencia bastante grande entre O (n) y O (nlogn). Es por eso que no es boundable por O (n) para cualquier constante.

Para ver una demostración gráfica:

Answer 3

Para más diversión en una vena similar, intente trazar el tiempo empleado por n las operaciones en el estándar conjunto disjunto estructura de datos . Se ha demostrado ser asintóticamente n α ( n ) donde α ( n ) es la inversa de la función de Ackermann (aunque su algoritmos habituales de libros de texto probablemente sólo mostrar una cota de n log log n o, posiblemente, n registro * n ). Para cualquier tipo de número que usted será probable que encuentre como el tamaño de entrada, α ( n ) ≤ 5 (y de hecho ingrese * n ≤ 5), aunque lo hace enfoque infinito asintótico.

Lo que supongo que se puede aprender de esto es que, si bien la complejidad asintótica es una herramienta muy útil para pensar acerca de los algoritmos, que no es exactamente lo mismo que la eficacia práctica.

Answer 4

1. lo general, el O (n * log (n)) algoritmos tienen una implementación logarítmica 2-base.
2. Para n = 1024, log (1,024) = 10, por lo que n * log (n) = 1024 * 10 = 10240 cálculos, un incremento en un orden de magnitud.

Así, O (n * log (n)) es similar a lineal sólo para una pequeña cantidad de datos.

Consejo:. No se olvide que la clasificación rápida se comporta muy bien en los datos aleatorios y que no es un O (n * log (n)) algoritmo

Answer 5

Todos los datos se pueden representar en una línea si los ejes se eligen correctamente: -)

Wikipedia dice Big-O es el peor de los casos (es decir, f (x) es O (N) significa f (x) es "acotado superiormente" por N) https://en.wikipedia.org/wiki/Big_O_notation

Aquí es un buen conjunto de gráficos que representan las diferencias entre las diversas funciones comunes: http://science.slc.edu/~jmarshall/courses/ 2002 / primavera / CS50 / O Mayúscula /

La derivada de log (x) es 1 / x. Se trata de cómo conectarse rápidamente (x) aumenta a medida que aumenta x. No es lineal, aunque pueda parecer una línea recta, ya que se dobla tan lentamente. Al pensar en O (log (n)), lo pienso como O (N ^ 0 +), es decir, la menor potencia de N que no es una constante, ya que cualquier potencia constante positiva de N superará eventualmente. No es fiable al 100%, por lo que los profesores tendrán enojado con usted si se le explica de esa manera.

La diferencia entre los registros de dos bases diferentes es un multiplicador constante. Busque la fórmula para la conversión de registros entre dos bases: (En "cambio de base" aquí: https://en.wikipedia.org/wiki/Logarithm) El truco es tratar a k y b como constantes.

En la práctica, hay normalmente va a haber algunos contratiempos en los datos que trama. Habrá diferencias en las cosas fuera de su programa (algo intercambiando en la CPU por delante de su programa, fallos de caché, etc.). Se necesitan muchas carreras para obtener datos fiables. Las constantes son el mayor enemigo de tratar de aplicar la notación O grande que el tiempo de ejecución real. Un algoritmo O (N) con una constante de alta puede ser más lento que un O (N ^ 2) algoritmo para lo suficientemente pequeño como N.

Answer 6

log (N) es (muy) más o menos el número de dígitos en N. Por lo tanto, para la mayor parte, hay poca diferencia entre log (n) y log (n + 1)

Answer 7

Trate de trazar una línea lineal real en la parte superior de la misma y verá el pequeño aumento. Tenga en cuenta que el valor de Y en 50,0000 es menor que el valor medio Y a 100.000.

Es allí, pero es pequeña. Lo cual es la razón por O (n log (n)) es tan bueno!