T(n) = 2T(n/2) + 0(1)
T(n) = T(sqrt(n)) + 0(1)
En la primera uso el método de sustitución para n, logn, etc .; todos me dieron respuestas incorrectas.
árboles de recurrencia: no sé si puedo aplicar ya que la raíz será una constante.¿Alguien puede ayudar a resolver esta relación de recurrencia?
¿Puede alguien ayudar?
Veamos el primero. Antes que nada, necesitas saber T (caso base). Mencionaste que es una constante, pero cuando haces el problema, es importante que lo anotes. Usualmente es algo como T (1) = 1. Lo usaré, pero puedes generalizar a lo que sea.
A continuación, descubra cuántas veces recurre (es decir, la altura del árbol de recursión). n es el tamaño de su problema, así que ¿cuántas veces podemos dividir repetidamente n por 2? En términos matemáticos, ¿qué ocurre cuando n/(2^i) = 1? Compruébelo, agárrelo para más tarde.
A continuación, haga algunas sustituciones, hasta que comience a notar un patrón.
T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)
Ok, el patrón es que multiplicamos T() por 2 un montón de veces, y dividir n por 2 un montón de veces. ¿Cuantas veces? i veces.
T(n) = (2^i)*T(n/(2^i)) + ...
Para los períodos de grandes θ al final, se utiliza un truco lindo. Mire arriba donde tenemos algunas sustituciones e ignore la parte T(). Queremos la suma de los θ términos. Tenga en cuenta que suman hasta (1 + 2 + 4 + ... + 2^i) * θ(1). ¿Puedes encontrar un formulario cerrado para 1 + 2 + 4 + ... + 2^i?Te daré ese; es (2^i - 1). Es bueno memorizar, pero here's how you'd figure it out.
De todos modos, todo en todo lo que tenemos
T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)
Si resuelve para i antes, entonces usted sabe que i = log_2(n). Conecta eso, haz algo de álgebra, y obtienes el
T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. Entonces T(n) = n + (n - 1)*θ(1). Que es n veces una constante, más una constante, más n. Soltamos términos y constantes de orden inferior, por lo que es θ (n).
Prasoon Saurav tiene razón sobre el uso del método maestro, pero es importante que sepa lo que está diciendo la relación de recurrencia. Las preguntas son: ¿cuánto trabajo debo hacer en cada paso y cuál es el número de pasos para una entrada de tamaño n?
Usa Master Theorem para resolver tales relaciones recurrentes.
Vamos un ser un número entero mayor que o igual a 1 y b ser un número real mayor que 1. Sea c ser un número real positivo y d un número real no negativo . Dada una recurrencia de la forma
T (n) = a T (n/b) + n c .. si n> 1
T (n) = d .. si n = 1
entonces para poder na de b,
- si log b un < c, T (n) = Θ (n c),
- si registro b a = c, T (n) = Θ (n c log n),
- si log b a> c, T (n) = Θ (n log b a).
1) T(n) = 2T(n/2) + 0(1)
En este caso
a = b = 2;
log b a = 1; c = 0 (desde n c = 1 => c = 0)
So Case (3) es aplicable.Así T(n) = Θ(n) :)
2) T(n) = T(sqrt(n)) + 0(1)
Let m = log n;
=> T (2 m) = T (2 m/2) + 0(1)
Ahora cambiar el nombre de K (m) = T (2 m) => K (m) = K (m/2) + 0(1)
Aplicar estuche (2).
¿Puedo aplicar el teorema de maestros incluso si f (n) es una constante, como en este caso 0 (1) ¿Qué pasa con el segundo problema? – rda3mon
@Ringo: Sí, puedes. Mira la edición. –
La parte 2 es incorrecta. Si '2^m = t', entonces' 2^(m/2) 'es nuevamente' sqrt (t) '. O más bien, '2^m = 2^log n = n', por lo que la sustitución no logró nada. – casablanca
Veamos la primera recurrencia, T (n) = 2T (n/2) + 1. El n/2 es nuestra idea aquí: parámetro de cada término anidado es la mitad de su matriz. Por lo tanto, si comenzamos con n = 2^k, tendremos k términos en nuestra expansión, cada uno sumando 1 al total, antes de llegar a nuestro caso base, T (0). Por lo tanto, suponiendo que T (0) = 1, podemos decir T (2^k) = k + 1. Ahora bien, dado que n = 2^k debemos tener k = log_2 (n). Por lo tanto, T (n) = log_2 (n) + 1.
Podemos aplicar el mismo truco a su segunda repetición, T (n) = T (n^0.5) + 1. Si comenzamos con n = 2^2^k tendremos k términos en nuestra expansión, cada uno sumando 1 al total. Suponiendo que T (0) = 1, debemos tener T (2^2^k) = k + 1. Dado que n = 2^2^k debemos tener k = log_2 (log_2 (n)), por lo tanto T (n) = log_2 (log_2 (n)) + 1.
Para la parte 1, puede utilizar Master Theorem como se sugiere @Prasoon Saurav.
Para la parte 2, justo expanda la recurrencia:
T(n) = T(n^1/2) + O(1) // sqrt(n) = n^1/2
= T(n^1/4) + O(1) + O(1) // sqrt(sqrt(n)) = n^1/4
etc.
La serie continuará k términos hasta n^1/(2^k) <= 1, es decir 2^k = log n o k = log log n. Eso da T(n) = k * O(1) = O(log log n).
¿cómo 2^k = log n lleva a k = log log n? – Irwin
@casablanca, ¿Puedes explicar cómo llegó <= 1? – TechCrunch
Las relaciones de recurrencia y las funciones recursivas también deben resolverse comenzando en f (1). En el caso 1, T (1) = 1; T (2) = 3; T (4) = 7; T (8) = 15; Está claro que T (n) = 2 * n -1, que en la notación O es O (n).
En el segundo caso T (1) = 1; T (2) = 2; T (4) = 3; T (16) = 4; T (256) = 5; T (256 * 256) = 6; Tomará poco tiempo descubrir que T (n) = log (log (n)) + 1 donde el log está en la base 2. Claramente esta es la relación O (log (log (n))
La mayoría de el tiempo de la mejor manera de hacer frente a la recurrencia es dibujar el árbol de recurrencia y cuidadosamente manejar el caso base.
Sin embargo aquí te daré ligero toque de resolver utilizando el método de sustitución.
En recurrencia primer intento de sustitución n = 2^k Reemplazo de segunda oportunidad de sustitución n = 2^2^k
Voy a votar para cerrar esta pregunta como fuera de tema porque es una pregunta matemática, no una pregunta de programación. – ProgramFOX