Alguien puede ayudar a resolver esta relación de recurrencia? [cerrado]

Question

T(n) = 2T(n/2) + 0(1)

T(n) = T(sqrt(n)) + 0(1)

En la primera utilizo método de sustitución para n, logn, etc; todo me dio respuestas incorrectas.
árboles de recurrencia:. No sé si es aplicable, como la raíz será una constante

Puede alguien ayuda?

Answer 1

Echemos un vistazo a la primera. En primer lugar, es necesario saber T (caso base). Usted ha mencionado que es una constante, pero cuando lo hace el problema es importante que lo escriba. Por lo general, se trata de algo como T (1) = 1. Voy a usar esto, pero se puede generalizar a lo que sea.

A continuación, averiguar cuántas veces recurrir (es decir, la altura del árbol recursividad). n es el tamaño del problema, por lo que el número de veces repetidas ocasiones podemos dividir n por 2? Matemáticamente hablando, ¿qué soy yo cuando n/(2^i) = 1? Figura hacia fuera, aferrarse a él para más tarde.

A continuación, hacer unas pocas sustituciones, hasta que empiece 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? veces i.

T(n) = (2^i)*T(n/(2^i)) + ...

Para los períodos de grandes ? al final, se utiliza un truco lindo. Mira por encima de donde tenemos unas pocas sustituciones, e ignorar la parte T (). Queremos que la suma de los términos theta. Tenga en cuenta que se suman a (1 + 2 + 4 + ... + 2^i) * θ(1). Se puede encontrar una forma cerrada para 1 + 2 + 4 + ... + 2^i? Te voy a dar que uno; es (2^i - 1). Es una buena para simplemente memorizan, pero aquí te mostramos cómo averiguarlo .

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). Enchufe que en, hacer un poco de álgebra, y se obtiene a

T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. Así T(n) = n + (n - 1)*θ(1). Que es n veces una constante, más una constante, más n. Dejamos términos y las constantes de orden inferior, por lo que es ? (n).

Prasoon Saurav es correcta sobre el uso del método maestro, pero es importante que usted sepa lo que la relación de recurrencia está diciendo. Las cosas que hacer son, la cantidad de trabajo hago en cada paso, y lo que es el número de pasos para una entrada de tamaño n?

Answer 2

Master Theorem para resolver este tipo de relaciones de recurrencia.

Let a ser un número entero mayor que o igual a 1 y b haber un mayor número real de 1. Sea c es un número real positivo y d un número real no negativo. Dada la recurrencia de la forma

• T (n) = a T (n / b) + n ^c .. si n> 1

• T (n) = d .. si n = 1

entonces para n una potencia de b,

1. si log _b a c ),
2. si log _b a = c, T (n) = T (n ^c log n),
3. si log _b a> c, T (n) = T (n ^{log _b a} ).

1) T(n) = 2T(n/2) + 0(1)

En este caso

a = b = 2;
log _b a = 1; c = 0 (puesto que n ^c = 1 => c = 0)

Así que la caja (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 la caja (2).

---

Answer 3

En la parte 1, se puede usar el Teorema Maestro como se sugiere @Prasoon Saurav.

En la parte 2, simplemente ampliar 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á términos k hasta n ^ 1/(2^k) <= 1, es decir 2^k = log n o k = log log n. Eso le da T(n) = k * O(1) = O(log log n).

Answer 4

Echemos un vistazo a 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 entonces tendremos k términos en nuestra expansión, cada uno añadiendo 1 al total, antes de chocar con nuestro caso base, T (0). Por lo tanto, suponiendo que T (0) = 1, podemos decir T (2 ^ k) = k + 1. Ahora, ya 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 empezamos con n = 2 ^ 2 ^ k tendremos k términos en nuestra expansión, cada uno añadiendo 1 a la total. Suponiendo T (0) = 1, debemos tener T (2 ^ 2 ^ k) = k + 1. Puesto que n = 2 ^ 2 ^ k debemos tener k = log_2 (log_2 (n)), por lo tanto, T (n) = log_2 (log_2 (n)) + 1.

Answer 5

relaciones de recurrencia y funciones recursivas, así debe ser resuelto por a partir de 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 O notación es O (n).
En segundo caso T (1) = 1; T (2) = 2; T (4) = 3; T (16) = 4; T (256) = 5; T (256 * 256) = 6; Se necesitará poco tiempo para descubrir que T (n) = log (log (n)) + 1 donde log es en base 2. Es evidente que esto es O (log (log (n)) relación.

Answer 6

La mayoría de las veces la mejor manera de hacer frente a la recurrencia es dibujar el árbol de recurrencia y cuidadosamente manejar el caso base.

Sin embargo aquí le daré el ligero toque de resolver utilizando método de sustitución.

En la recurrencia primer intento n = 2^k sustitución En recurrencia segundo intento de sustitución n = 2^2^k