¿Qué es O (nlog (n)) de notación big-O? ¿Cuáles son algunos ejemplos de sus algoritmos?

Encuentro lo siguiente muy útil para comprender la notación Big O y el rendimiento relativo de los algoritmos a medida que N aumenta. El último gráfico es particularmente valioso porque explica por qué nos preocupamos por Big O en primer lugar.

[math] O (nlogn) [/ math] contiene un [math] logn [/ math]; por lo tanto, debe haber algo relacionado con estructuras binarias o divide y vencerás.

Hay muchos ejemplos.

Por ejemplo, el ordenamiento dinámico es un algoritmo de clasificación [matemático] O (nlogn) [/ matemático] muy famoso. Y la complejidad de Tarjan LCA (Offline LCA) es [math] O (n) [/ math] ~ [math] O (nlogn) [/ math]. La complejidad de construir un árbol de segmentos es [matemática] O (nlogn) [/ matemática]. Además, el preprocesamiento ST (tabla dispersa) para RMQ (consulta de rango máximo / mínimo) es [matemática] O (nlogn) [/ matemática] etc.

Por lo general, [math] logn [/ math] representa [math] log_2n [/ math] porque la mayoría de esas estructuras son estructuras de datos binarios. Y una vez que [math] logn [/ math] se presenta en la complejidad, debe haber algo relacionado con estructuras o algoritmos binarios (Binary Search, por ejemplo).

La transformada discreta rápida de Fourier (FFT) es O (n * log (n)), que fue una gran

mejora sobre la ingenua versión O (n ^ 2) del algoritmo

(n ^ 2 es n al cuadrado)

La mejor conceptualización que se me ocurre es que [matemáticas] O (n * log_b (N)) [/ matemáticas] implica que está visitando cada elemento de un árbol equilibrado con hasta [matemáticas] b [/ matemáticas] niños en cada nodo, pero cada vez que desee acceder a un nodo, debe comenzar desde la raíz. Por lo tanto, necesita [math] log_b (N) [/ math] tiempo para descender el árbol hasta llegar a un solo elemento, y está haciendo esto [math] N [/ math] veces en general.

Tenga en cuenta que en la mayoría de las situaciones, [math] b [/ math] está implícito en 2. Por ejemplo, en QuickSort, en cada etapa, la lista se divide en 2.

Big O denota la peor complejidad del caso. La peor complejidad del caso significa que, en cualquier caso, su programa no cruzará el tiempo O (nlogn). Hay muchos Algo que toman tiempo O (nlogn). Uno de estos algoritmos de clasificación es la combinación de clasificación, que es un algoritmo de división y conquista, y toma O (nlogn) en todos los casos. La ordenación por fusión es eficiente para un gran tamaño de entrada.