¿Cuál es la diferencia entre O (n!) Vs O (2 ^ n) complejidad de tiempo?

O (n!) Le da muchos más recursos (en términos de tiempo) al solucionador.

Verifique las siguientes tres figuras:

Figura 1: Justo después de n = 3, la clase factorial toma la delantera.

Figura 2: Aumente la diferencia de recursos muy rápidamente justo después de 5 pasos más.

Figura 3: La clase factorial muestra la clase exponencial como una sola partícula de arena en comparación con el Monte Himalaya. Y esto es justo cuando su entrada es de solo 15 unidades.

Como puede observar, a medida que aumenta el tamaño de entrada, también lo hace la diferencia en una “velocidad factorial”.

Básicamente, la jerarquía de tiempo dice que cuantos más recursos de tiempo tenga, más problemas podrá resolver.

Aquí está la diferencia:

para saber la diferencia, intente mostrar un ^ n

Cuando registra ambos lados obtiene: n log a

cuando n crece, agregas números grandes arbitrarios a la derecha mientras que la izquierda se multiplica por la misma constante … así que está claro cuál crece más rápido …

El gráfico muestra la tasa de aumento para algunos de los grandes tiempos comunes de O.

Como puede ver, 0 (x!) Es mucho peor que O (2 ^ x). Hay muchos
de tiempos de ejecución peores que 0 (x!) también, como O (x ^ x) u O (2x * x!).

La aproximación de Stirling para n! es proporcional a n ^ n – esto es mayor que 2 ^ n

Tiempo completamente O (n!) Es mayor que O (2 ^ n)
Entonces, un programa con complejidad de tiempo O (2 ^ n) es más eficiente.