n * log ny n / log n contra el tiempo de ejecución polinómico

Entiendo que es más rápido que Θ ( n log n ) y más lento que Θ ( n / log n ) . Lo que me resulta difícil de entender es cómo comparar Θ ( n log n ) y Θ ( n / log n ) con Θ ( n f ) donde 0 < f < 1 .$\Theta(n)$$\Theta(n\log n)$$\Theta(n/\log n)$$\Theta(n \log n)$$\Theta(n/\log n)$$\Theta(n^f)$$0 < f < 1$

Por ejemplo, ¿cómo decidimos vs. Θ ( n 2 / 3 ) o Θ ( n 1 / 3$\Theta(n/\log n)$$\Theta(n^{2/3})$$\Theta(n^{1/3})$

Me gustaría tener algunas instrucciones para proceder en tales casos. Gracias.

Si solo dibuja un par de gráficos, estará en buena forma. Wolfram Alpha es un gran recurso para este tipo de investigaciones:

Generado por este enlace . Tenga en cuenta que en el gráfico, log (x) es el logaritmo natural, razón por la cual la ecuación de un gráfico se ve un poco divertida.

es el inverso de 2 n . Así como 2 n crece más rápido que cualquier polinomio n k, independientemente de cuán grande sea una k finita, log n crecerá más lentamente que cualquier función polinomial n k, independientemente de cuán pequeño sea un cero positivo, k .$\log n$$2^n$$2^n$$n^k$$k$$\log n$$n^k$$k$

$n / \log n$$n^k$$k < 1$$n / \log n$$n / n^{1-k}$

$n^{1-k} > \log n$$n$$n / \log n > n^k$$k < 1$$n$

Para muchos algoritmos, a veces sucede que las constantes son diferentes, lo que hace que una u otra sea más rápida o más lenta para tamaños de datos más pequeños, y no están tan bien ordenadas por la complejidad algorítmica.

Dicho esto, si solo consideramos los tamaños de datos súper grandes , es decir. cuál finalmente gana, luego O(n^f)es más rápido que O(n/log n)para 0 < f < 1.

Una gran parte de la complejidad algorítmica es determinar qué algoritmo es finalmente más rápido, por lo tanto, saber que O(n^f)es más rápido que O(n/log n)para 0 < f < 1, a menudo es suficiente.

Una regla general es que multiplicar (o dividir) por log neventualmente será insignificante en comparación con multiplicar (o dividir) por n^fcualquiera f > 0.

Para mostrar esto más claramente, consideremos lo que sucede cuando n aumenta.

   n       n / log n         n^(1/2)
   2        n/ 1              ?
   4        n/ 2             n/ 2
   8        n/ 3              ?
  16        n/ 4             n/ 4
  64        n/ 6             n/ 8
 256        n/ 8             n/16
1024        n/10             n/32

¿Notar cuál disminuye más rápidamente? Es la n^fcolumna.

Incluso si festuviera más cerca de 1, la n^fcolumna comenzará más lentamente, pero a medida que n se duplica, la velocidad de cambio del denominador se acelera, mientras que el denominador de la n/log ncolumna parece cambiar a una velocidad constante.

Tracemos un caso particular en un gráfico

Fuente: Wolfram Alpha

Seleccioné O(n^k)tal que kestá bastante cerca de 1 (at 0.9). También seleccioné las constantes para que inicialmente O(n^k)sea ​​más lento. Sin embargo, tenga en cuenta que finalmente "gana" al final, y lleva menos tiempo que O(n/log n).

$n^f$$\dfrac{n}{n^{1-f}}$$n^{2/3}=n/n^{1/3}$

$\log n$$n^\varepsilon$$\varepsilon>0$

Al comparar los tiempos de ejecución, siempre es útil compararlos utilizando grandes valores de n. Para mí, esto ayuda a desarrollar la intuición sobre qué función es más lenta

En su caso, piense en n = 10 ^ 10 y a = .5

O(n/logn) = O(10^10/10) = O(10^9)
O(n^1/2) = O(10^10^.5) = O(10^5)

Por lo tanto, O (n ^ a) es más rápido que O (n / logn), cuando 0 <a <1 he usado solo un valor, sin embargo, puede usar múltiples valores para construir la intuición sobre la función

$f \prec g$

$(2, 10) < (3, 5)$$(2, 10) > (2, 5)$

Aplicado a su ejemplo:

$\mathcal{O}(n/\log n) \Rightarrow (1, -1, 0)$

$\mathcal{O}(n^{2/3}) \Rightarrow (2/3, 0, 0)$

$\mathcal{O}(n^{1/3}) \Rightarrow (1/3, 0, 0)$

Se podría decir: los poderes de n dominan los poderes del registro, que dominan los poderes del registro.

Fuente: Matemáticas concretas, p. 441