Estoy tratando de entender qué está mal con la siguiente prueba de la siguiente recurrencia
La documentación dice que está mal debido a la hipótesis inductiva de que
¿Qué me estoy perdiendo?
Estoy tratando de entender qué está mal con la siguiente prueba de la siguiente recurrencia
La documentación dice que está mal debido a la hipótesis inductiva de que
Respuestas:
Digamos que el objetivo final es probar . Comienzas con la hipótesis de inducción:T(n)=O(n)
para todo i < n .T(i)≤ci i<n
Y para completar la prueba, debe demostrar que también.T(n)≤cn
Sin embargo, lo que puede deducir es , que no es útil para completar la prueba; necesitas una constante c para (casi) todas las n . Por lo tanto, no podemos concluir nada y T ( n ) = O ( n ) no está probado.T( n ) ≤ ( c + 1 ) n C norte T( n ) = O ( n )
Tenga en cuenta que está confundido entre el resultado y el proceso de prueba. Y un punto más, es en realidad Θ ( n log n ) en este caso, por lo que puede considerar una hipótesis de inducción adecuada para poder probarla.T( n ) Θ ( n logn )
fuente
Has omitido algunos pasos. Parece que está intentando demostrar por inducción que , y su prueba es:T( n ) = O ( n )
Esta prueba sale mal desde el principio: " para k < n " no tiene sentido. Big oh es una noción asintótica: T ( k ) = O ( k ) significa que hay una constante c y un umbral N tal que ∀ k ≥ N , T ( k ) ≤ cT( k ) = O ( k ) k < n T( k ) = O ( k ) C . Y de nuevo al final, no puede concluir que " T ( n ) = O ( n ) ", porque eso dice algo sobre la función T en su conjunto y solo ha demostrado algo sobre el valor particular T ( n ) .∀k≥N,T(k)≤ck T(n)=O(n) T T(n)
Debe ser explícito sobre lo que significa Entonces tal vez tu prueba sea:O
Esto no prueba un paso inductivo: comenzaste desde , y usted demostró que para k = n , T ( k ) ≤ ( c + 1 )T(k)≤ck k=n . Este es un límite más débil. Mira lo que esto significa: T ( k ) ≤ cT(k)≤(c+1)k medios que c es un límite para la tasa de crecimiento de T . Pero tienes una tasa c que crece cuando k crece. ¡Eso no es un crecimiento lineal!T(k)≤ck c T c k
Si observa detenidamente, notará que la tasa aumenta en 1 cada vez que k se duplica. Entonces, informalmente, si m = 2 p k entonces c m = c k + p ; en otras palabras, c k = c 0 log 2 k .c 1 k m=2pk cm=ck+p ck=c0log2k
Esto puede hacerse preciso. Demuestre por inducción que para , T ( k ) ≤ c log 2 ( k ) .k≥1 T(k)≤clog2(k)
La relación de recurrencia es típica para los algoritmos de divide y vencerás que dividen los datos en dos partes iguales en tiempo lineal. Dichos algoritmos operan en tiempo (no O ( n ) ).Θ(nlog(n)) O(n)
Para ver cuál es el resultado esperado, puede verificar la relación de recurrencia con el teorema maestro . La división es y el trabajo extra realizado es n ; log 2 ( 2 ) = 1, entonces este es el segundo caso para el que el crecimiento es Θ ( n2T(n/2) n log2( 2 ) = 1 .Θ ( nIniciar sesión( n ) )
fuente
Extiendo la respuesta ya dada, quizás solo explicando mi comentario con más detalle.
Como adivinar puede ser claramente difícil y tedioso, a veces existen mejores métodos. Uno de esos métodos es el Teorema Maestro . Nuestra recurrencia es ahora de la forma , donde un ≥ 1 y b > 1 son constantes y f ( n ) una función. Tenga en cuenta que en nuestro caso ⌊ n / 2 ⌋ puede interpretarse en el sentido de n / 2T( n ) = a T( n / b ) + f( n ) a ≥ 1 b > 1 F( n ) ⌊ n / 2 ⌋ n / 2 . Para ser técnicamente exactos, nuestra recurrencia podría no estar bien definida porque podría no ser un número entero. Sin embargo, esto está permitido ya que no afectará el comportamiento asintótico de la recurrencia. Por lo tanto, a menudo nos parece conveniente dejar caer pisos y techos. La prueba formal de esto es un poco tediosa, pero el lector interesado puede encontrarla, por ejemplo, en Cormen et al. libro .n / 2
En nuestro caso, tenemos , b = 2 , f ( n ) = Θ ( n ) . Esto significa que tenemos n log b a = n log 2 2 = n . El segundo caso del teorema maestro se aplica ya que f ( n ) = Θ ( n ) , y tenemos la solución T ( n ) = Θ ( n loga = 2 b = 2 F( n ) = Θ ( n ) norteIniciar sesiónsiun= nIniciar sesión22= n F( n ) = Θ ( n ) .T( n ) = Θ ( n logn )
fuente