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

Para su información, quicksort es en realidad O (n^2), pero con un caso promedio de O(nlogn)

Para su información, hay una diferencia bastante grande entre O(n) y O(nlogn). Es por eso que no es enlazable por O(n) para cualquier constante.

Para una demostración gráfica ver:

Para aún más diversión en una vena similar, intente trazar el tiempo tomado por n operaciones en el estándar disjoint set data structure. Se ha demostrado para ser asintóticamente n α(n) donde α(n) es la inversa de la Ackermann función (a pesar de su habitual algoritmos de libros de texto probablemente sólo mostrar un límite de n log log n o, posiblemente, n registro de* n). Para cualquier tipo de número que usted será probable para encontrar como tamaño de entrada, α (n) ≤ 5 (y de hecho log* n ≤ 5), aunque se acerca al infinito asintóticamente.

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

1. Normalmente los algoritmos O( n*log(n) ) tienen una implementación logarítmica de 2 bases.
2. Para n = 1024, log(1024) = 10, por lo que n*log(n) = 1024*10 = 10240 cálculos, un aumento en un orden de magnitud.

Entonces, O(n*log(n)) es similar a lineal solo para una pequeña cantidad de datos.

Consejo: no olvides que quicksort se comporta muy bien en datos aleatorios y que no es un algoritmo O(n*log(n)).

Cualquier dato se puede trazar en una línea si los ejes se eligen correctamente: -)

Wikipedia dice que Big-O es el peor caso(es decir, f(x) es O(N) significa que f (x) está "delimitado por encima" por N) https://en.wikipedia.org/wiki/Big_O_notation

Aquí hay un buen conjunto de gráficos que representan las diferencias entre varias funciones comunes: http://science.slc.edu / ~jmarshall / courses / 2002 / spring / cs50 / BigO /

La derivada de log (x) es 1 / x. Esta es la rapidez con la que log (x) aumenta como x aumentar. No es lineal, aunque puede parecer una línea recta porque se dobla muy lentamente. Cuando pienso en O (log (n)), pienso en ella como O(N^0+), es decir, la potencia más pequeña de N que no es una constante, ya que cualquier potencia constante positiva de N la superará eventualmente. No es 100% exacto, así que los profesores se enojarán contigo si lo explicas de esa manera.

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

En la práctica, normalmente va a haber algunos contratiempos en cualquier dato que trace. Habrá diferencias en las cosas fuera de su programa (algo que se intercambia en la cpu antes de su programa, errores de caché, etc.). Se necesitan muchas carreras para obtener datos confiables. Las constantes son el mayor enemigo de tratar de aplicar la notación Big O al tiempo de ejecución real. An O (N) el algoritmo con una constante alta puede ser más lento que un algoritmo O(N^2) para N.

Log (N) es (muy) aproximadamente el número de dígitos en N. Por lo tanto, en su mayor parte, hay poca diferencia entre log(n) y log(n+1)

Intente trazar una línea lineal real encima de ella y verá el pequeño aumento. Tenga en cuenta que el valor Y en 50,0000 es menor que el valor 1/2 Y en 100,000.

Está ahí, pero es pequeño. Por eso O(nlog(n)) es tan bueno!