Método de adivinar y confirmar

La idea básica detrás de este método es adivinar la respuesta y luego demostrar que es correcta por inducción. Este método se puede utilizar para resolver cualquier recurrencia. Si se adivina una solución y luego se intenta verificar nuestra suposición de manera inductiva, por lo general, la prueba tendrá éxito (en ese caso hemos terminado) o la prueba fallará (en ese caso, la falla nos ayudará a refinar nuestra suposición).

Por ejemplo, considere la recurrencia: $T(N) = √N*T(√N) + N$ . Esto no encaja en la forma requerida por los Teoremas Maestros . Observar cuidadosamente la recurrencia nos da la impresión de que es similar al método divide y vencerás (dividir el problema en √N subproblemas cada uno con tamaño √N ). Como puede verse, el tamaño de los subproblemas en el primer nivel de recursión es N . Entonces, supongamos que $T(N) = O(N*log N)$ , y luego tratemos de probar que la suposición es correcta.

Comencemos tratando de probar un límite superior:

$T(N) \le cN*logN:$

$T(N) = √N*T(√N) + N$

$T(N) \le √N* c√N*log√N + N$

$T(N) = N* clog√N + N$

$T(N) = N*1/2*c*log N + N$

$T(N) \le cN*log N$

La última desigualdad supone sólo que $1 \le 1/2*clog N$ . Esto es correcto si N es suficientemente grande y para cualquier constante c, por pequeña que sea.

De la prueba anterior, podemos ver que nuestra suposición es correcta para el límite superior. Ahora, probemos el límite inferior para esta recurrencia:

$T(N) = √N*T(√N) + N$

$T(N) \ge √N* k√N*log√N + N$

$T(N) = N* klog√N + N$

$T(N) = N*1/2*k*log N + N$

$T(N) \ge N*k*log N$

La última desigualdad supone sólo que $1 \ge 1/2*k*log N$ . Esto es incorrecto si N es suficientemente grande y para cualquier constante k.

De la prueba anterior, podemos ver que nuestra suposición es incorrecta para el límite inferior.

De la discusión anterior, se puede entender que $Θ(N*log N)$ es demasiado grande. Pero ¿qué tal $Θ(N)$ ? El límite inferior es fácil de probar directamente:

$T(N) = √N*T(√N) + N \ge N$

Ahora, probemos el límite superior para este Θ(N):
$T(N) = √N*T(√N) + N\\ \le √N*c√N + N\\ = N c+ N\\ = N (c + 1)\\ \nleq cN$

De la inducción anterior, se puede entender que $Θ(N)$ es demasiado pequeño y $Θ(N*log N)$ demasiado grande. Entonces, necesitamos algo más grande que N y más pequeño que $N*log N$ ? ¿Qué tal $N*√log N$ ?

Demostrando el límite superior para $N*√log N$ :

$T(N) = √N*T(√N) + N$

$T(N) \le √n*c√N*√(log √N) + N$

$T(N) = N* 1/√2 *c*log √N + N$

$T(N) \le N*c*log √N$

Demostrando límite inferior para $N*√log N$ :

$T(N) = √N*T(√N) + N$

$T(N) \ge √N*k√N*√(log√N) + N$

$T(N) = N*1/√2*k*log √N + N$

$T(N) \ngeq N*k*log √N$

El último paso no funciona. Entonces, $Θ(N*√log N)$ no funciona. ¿Qué más hay entre N y $N*log N$ ? ¿Qué tal $N*log(log N)$ ?

Demostrando el límite superior para $N*log(log N)$ :

$T(N) = √N*T(√N) + N$
$T(N) \le √N*c√N*log(log √N) + N$
$T(N) = N*clog(log N) - cN + N$
$T(N) \le N*clog(log N), if \ c\ge 1$

Demostrando límite inferior para $N*log(log N)$ :

$T(N) = √N*T(√N) + N$

$T(N) \ge √N*k√N*log(log √N) + N$

$T(N) = N*k*log(log N) - kN + N$

$T(N) \ge N*klog(log N), if \ k \le 1$

De las pruebas anteriores, puede ver que $T(N) \le N*clog(log N), if \ c \ge 1$ y $T(N) \ge N*klog(log N), if \ k \le 1$ .
Técnicamente, todavía nos faltan los casos base en ambas pruebas, pero podemos estar bastante seguros en este punto de que $T(N) = Θ(N*log(log N))$ .

Publicación traducida automáticamente

Artículo escrito por gauravkmishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta