¿Cuál es la complejidad de [matemáticas] T (n) = 4T (\ frac {n} {2}) + \ theta (n) [/ matemáticas]?

Answer 1

Si usa el teorema del Maestro, obtiene [matemáticas] \ Theta (n ^ 2) [/ matemáticas]

Editar: si desea una explicación más intuitiva, piense así:

Empiezas con una x arbitraria, y asumes tu función [matemáticas] \ Theta (n) = n [/ matemáticas] para que se vea así:

[matemáticas] T (x) = 4T (x / 2) + x = 4 (4 (T (x / 4) + (x / 2)) + x = 16T (x / 4) + 2x + x [/ matemáticas ]

[matemáticas] = 16 (4 (T (x / 8) + (x / 4)) + 2x + x [/ matemáticas]

[matemática] = 64T (x / 8) + 4x + 2x + x [/ matemática]

y así

Muy rápidamente, puede ver un patrón que se forma, que es

[matemáticas] T (x) = x + 2x + 4x + 8x +… [/ matemáticas] (hasta que su recurrencia llegue a su caso base)

Esto es solo una serie geométrica.

Entonces puedes resumir eso para obtener algo como

[matemáticas] T (x) = x (1 + 2 + 4 + 8 +…) = x \ frac {2 ^ {log_2 (x)} – 1} {2 – 1} = x (x-1) \ aprox x ^ 2 [/ matemáticas]

(Hay [math] log_2 (x) [/ math] pasos porque está reduciendo a la mitad el tamaño de recurrencia en cada paso)

Entonces obtienes una función [math] \ Theta (x ^ 2) [/ math]

Answer 2

Ampliando un poco, vemos que

[matemáticas] T (n) = 4 ^ kT (n / 2 ^ k) + k \ Theta (n) [/ matemáticas]

(ignorando las constantes porque es [matemáticas] \ Theta (n) [/ matemáticas]).

Cuando [math] k = \ log n [/ math], la recursión toca fondo. Por lo tanto, el término de la derecha se convierte en [matemáticas] \ Theta (n \ log n). [/matemáticas]

El término izquierdo es [matemáticas] 4 ^ {\ log n} T (1) [/ matemáticas]. [math] T (1) [/ math] es constante, por lo que solo necesitamos determinar si [math] 4 ^ {\ log n} [/ math] es más grande o más pequeño que [math] n \ log n [/ math] . Observando que [matemáticas] 4 ^ {\ log n} = 2 ^ {2 \ log n} = 2 ^ {\ log n ^ 2} = n ^ 2 = \ Theta (n ^ 2) [/ matemáticas], concluimos que domina el término correcto, entonces [matemáticas] T (n) = \ Theta (n ^ 2) [/ matemáticas].

Answer 3

Usando el teorema del maestro

[matemáticas] T (n) = aT (\ dfrac {n} {b}) + \ theta (n ^ c) [/ matemáticas]

Puede haber tres casos:

• [math] log_b a> c \ longrightarrow T (n) = \ theta (n ^ {log_b a}) [/ math]
• [math] log_b a = c \ longrightarrow T (n) = \ theta (n ^ {log_b a} log n) [/ math]
• [matemáticas] log_b a

En nuestro caso

• a = 4
• b = 2
• c = 1

Entonces es el primer caso del Teorema del Maestro

[math] log_2 4> 1 \ longrightarrow T (n) = \ theta (n ^ 2) [/ math]