¡Puedes resolver este problema con una simple sustitución!
[matemáticas] T (n) = T (\ sqrt {n}) + \ log {n} [/ matemáticas]
Sustituyendo [matemáticas] n = 2 ^ {m} [/ matemáticas], obtenemos:
- ¿Cuáles son los mejores algoritmos y estructuras de datos MOOC?
- ¿Cuál es el algoritmo más ineficiente para los estándares actuales que se usa ampliamente en la industria?
- Cómo encontrar el número de subárboles izquierdo y derecho de un árbol binario
- ¿Cuáles son algunas estructuras de datos que debo aprender?
- ¿Hay diseñadores que diseñan algoritmos?
[matemáticas] T (n) = T (2 ^ {m}) = T (\ sqrt {2 ^ {m}}) + \ log {2 ^ {m}} = T (2 ^ {m / 2}) + m [/ matemáticas]
Deje que [matemática] S (m) [/ matemática] se defina como [matemática] S (m) = T (2 ^ m) = T (2 ^ {m / 2}) + m [/ matemática]. (*)
Tenga en cuenta que [matemáticas] S (m / 2) = T (2 ^ {m / 2}) [/ matemáticas], entonces por (*):
[matemáticas] S (m) = S (m / 2) + m [/ matemáticas].
Ahora puede usar el Teorema maestro para resolver esta recursión en términos de [matemáticas] S (m) [/ matemáticas], para obtener:
[matemáticas] S (m) = \ Theta (m) [/ matemáticas]
También podría haber deducido este resultado al observar que en su recursión, combinar los subproblemas lleva tiempo [matemático] \ Theta (m) [/ matemático], que domina el tiempo que tarda la recursión en ejecutarse (tiempo logarítmico).
Para finalizar, sustituimos [math] m = \ log {n} [/ math] para obtener:
[matemáticas] S (m) = T (2 ^ m) = T (2 ^ {\ log {n}}) = T (n) = \ Theta (m) = \ Theta (\ log {n}). [ /mates]
Despejando el desorden, [matemáticas] T [/ matemáticas] [matemáticas] (n) = \ Theta (\ log {n}) [/ matemáticas]
