Error en el uso de notación asintótica

10

Estoy tratando de entender qué está mal con la siguiente prueba de la siguiente recurrencia

T(n)=2T(n2)+n
T(n)2(cn2)+ncn+n=n(c+1)=O(n)

La documentación dice que está mal debido a la hipótesis inductiva de que

T(n)cn
¿Qué me estoy perdiendo?
Erb
fuente
2
Las recurrencias de esta forma también se pueden resolver utilizando el teorema del maestro .
Juho
2
@Ran: No creo que el teorema maestro sea una etiqueta apropiada para esta pregunta. La pregunta no es cómo resolverlo, sino señalar la falacia en un argumento particular. Además, el teorema maestro es probablemente demasiado específico y probablemente no merece tener su propia etiqueta. En general, deberíamos etiquetar según la pregunta, no las respuestas posibles. Por ejemplo, ¿etiquetarías este akra-bazzi?
Aryabhata
"lo que está mal con la siguiente prueba" - No veo una prueba. A menudo es útil escribir una prueba completa (es decir, hacer que la inducción sea explícita) para detectar errores.
Raphael
Una pregunta más general relacionada es Resolver o aproximar relaciones de recurrencia para secuencias de números .
Juho

Respuestas:

12

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)cii<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)ncnT(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)Θ(nlogn)

almohadilla
fuente
si reemplazamos c '= c + 1, ¿hará algún cambio?
Erb
@erb: No, no lo hará. Tienes que probar para una constante elegida. Si reemplaza , eventualmente tiene T ( n ) ( c + 1 ) n (o T ( n ) ( c + 2 ) n ), entonces el resultado es el mismo. c=c+1T(n)(c+1)nT(n)(c+2)n
pad
8

Has omitido algunos pasos. Parece que está intentando demostrar por inducción que , y su prueba es:T(n)=O(n)

Suponga que para k < n . Esto significa T ( k ) cT(k)=O(k)k<n para algunos c . Entonces T ( n ) = 2 T ( n / 2 ) + n 2 c n / 2 + n ( c + 1 )T(k)ckc , entonces T ( n ) = O ( n ) .T(n)=2T(n/2)+n2cn/2+n(c+1)nT(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<nT(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 ) .kN,T(k)ckT(n)=O(n)TT(norte)

Debe ser explícito sobre lo que significa Entonces tal vez tu prueba sea:O

Suponga que para todo k < n . Entonces T ( n ) = 2 T ( n / 2 ) + n 2 c n / 2 + n ( c + 1 )T(k)Ckk<norte .T(norte)=2T(norte/ /2)+norte2Cnorte/ /2+norte(C+1)norte

Esto no prueba un paso inductivo: comenzaste desde , y usted demostró que para k = n , T ( k ) ( c + 1 )T(k)Ckk=norte . 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)CkCTCk

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 .C1kmetro=2pagskCmetro=Ck+pagsCk=C0 0Iniciar sesión2k

Esto puede hacerse preciso. Demuestre por inducción que para , T ( k ) c log 2 ( k ) .k1T(k)CIniciar sesión2(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 ) ).Θ(nortelosol(norte))O(norte)

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(norte/ /2)norteIniciar sesión2(2)=1 .Θ(norteIniciar sesión(norte))

Gilles 'SO- deja de ser malvado'
fuente
7

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(norte)=unT(norte/ /si)+F(norte)un1si>1F(norte)norte/ /2norte/ /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 .norte/ /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 logun=2si=2F(norte)=Θ(norte)norteIniciar sesiónsiun=norteIniciar sesión22=norteF(norte)=Θ(norte) .T(norte)=Θ(norteIniciar sesiónnorte)

Juho
fuente
¡Gracias! Cabe señalar que "dejar caer pisos y techos" corresponde a suponer que cual se hace comúnmente. La observación básica es que para funciones no decrecientes, el crecimiento asintótico de subsecuencias es igual al crecimiento asintótico de toda la secuencia. norte=2k
Raphael