T (n) = 16T (n / 4) + n!
Entonces a = 16, b = 4 yf (n) = n!
[matemáticas] \ log_b {a} [/ matemáticas] = [matemáticas] \ log_4 {16} [/ matemáticas] = 2
Entonces [matemáticas] n ^ {\ log_b {a}} [/ matemáticas] = [matemáticas] n ^ 2 [/ matemáticas]
- ¿Sigue siendo relevante el modelado de objetos, o se ha reemplazado hoy solo con datos y algoritmos?
- Dada una lista de enlaces con punteros derechos, cada elemento de la lista tiene un enlace descendente que contiene otra lista de enlaces con punteros descendentes, de modo que cada lista derecha y abajo están ordenadas. ¿Cuál es la forma más rápida de aplanar la lista de enlaces de forma ordenada?
- ¿Cuándo se debe comenzar a resolver los problemas del Proyecto Euler en HackerRank? He resuelto alrededor de 50 en SPOJ, entonces, ¿es el momento adecuado para comenzar?
- ¿Qué compañías necesitan algoritmos de flujo óptico fuertes?
- Cómo diseñar un algoritmo de movimiento para un robot hexápodo
Tercer caso del teorema maestro:
f (n) = [matemática] \ Omega (n ^ {\ log_b {a} + e}) [/ matemática] para alguna constante [matemática] \ epsilon [/ matemática]> 0.
y si af (n / b) <= cf (n) para alguna constante c <1 y todas suficientemente grandes n, entonces T (n) = [matemática] \ Theta [/ matemática] (f (n)) (condición de regularidad )
Por lo tanto n! = [matemáticas] \ Omega (n ^ {2 + \ epsilon}) [/ matemáticas]
Se podría demostrar que esto satisface algún valor de [math] \ epsilon [/ math]> 0 usando la aproximación de Stirling
Para la condición de regularidad,
16f (n / 4) <= cf (n)
es decir, 16 (n / 4)! <= cn!
¡Tome c = 0.5 y encontrará que la condición de regularidad satisface!
Por lo tanto, según el caso 3, T (n) = [matemáticas] \ Theta (n!) [/ Matemáticas] 🙂
