¿Por qué existe la condición de regularidad en el teorema maestro?

15

He estado leyendo Introducción a los algoritmos de Cormen et al. y estoy leyendo la declaración del teorema del Maestro que comienza en la página 73 . En el caso 3 también hay una condición de regularidad que debe cumplirse para usar el teorema:

... 3. Si

f(n)=Ω(nlogba+ε)

para alguna constanteε>0 y si

af(n/b)cf(n)      [esta es la condición de regularidad]

para alguna constante y para todo lo suficientemente grande n , entonces ..c<1n

¿Alguien puede decirme por qué se necesita la condición de regularidad? ¿Cómo falla el teorema si la condición no se cumple?

Rafael
fuente
¿Puedes escribir cuál es el caso y cuál es la condición reglamentaria?
3
No tengo una respuesta definitiva para usted, pero parece que si la condición de regularidad no se cumple, entonces los subproblemas toman más y más tiempo cuanto más pequeños son, por lo que obtiene una complejidad infinita.
No estoy seguro de que la condición de regularidad sea necesaria para que se mantenga la conclusión del teorema, pero creo que es necesaria para la prueba utilizada. Con la condición de regularidad, tiene una prueba bastante sencilla, sin ella, al menos sería peluda.

Respuestas:

10

No es una prueba rigurosa, sino una explicación "desde la cima de mi cabeza".

Imagine la recurrencia como un árbol. El tercer caso cubre el escenario cuando el nodo raíz domina el tiempo de ejecución asintóticamente, es decir, la mayor parte del trabajo se realiza en un nodo miserable en la parte superior del árbol de recurrencia. Entonces el tiempo de ejecución es Θ ( f ( n ) ) .aT(n/b)+f(n)Θ(f(n))

Para asegurarse de que la raíz realmente hace más trabajo, necesita el

.af(n/b)cf(n)

Esto dice que (la cantidad de trabajo realizado en la raíz) debe ser al menos tan grande como la suma del trabajo realizado en los niveles inferiores. (La recurrencia se llama a veces en n / b de la entrada.)f(n)an/b

Por ejemplo, para la recurrencia el trabajo en el nivel debajo de la raíz es un cuarto como grande y solo se realiza dos veces ( n / 4 + n / 4 ) versus n para que la raíz domine .T(n)=2T(n/4)+n(n/4+n/4)n

Pero, ¿qué pasa si la función no cumple la condición de regularidad? Por ejemplo, lugar de n ? Entonces, el trabajo realizado en los niveles inferiores puede ser mayor que el trabajo realizado en la raíz, por lo que no está seguro de que la raíz domine.cos(n)n

El gato no divertido
fuente
3
Usé un mejor formato para su texto matemático. Puede hacer clic en el enlace "editado" y ver lo que hice.
Juho
7

Deje y b = 2 , de modo que T ( 2 n ) = n Σ k = 0 f ( 2 k ) . Para que se aplique el caso 3, necesitamos f ( n ) = Ω ( n ϵ ) (para algunos ϵ > 0 ) y la condición de regularidad, f ( n / 2 ) ( 1 - δ ) fun=1si=2

T(2norte)=k=0 0norteF(2k).
F(norte)=Ω(norteϵ)ϵ>0 0 (para algunos δ > 0 ). Obtiene la condición de regularidad de la prueba, es decir, es un concepto generado por la prueba. Si bien la condición de regularidad no es necesaria (considere el ejemplo dado en Wikipedia, f ( n ) = n ( 2 - cos n ) ), no puede eliminarlo por completo, como lo demuestra el siguiente ejemplo. Considere f ( 2 n ) = 2 2 log 2 n > 2 2 log 2 n -F(norte/ /2)(1-δ)F(norte)δ>0 0F(norte)=norte(2-cosnorte)
F(2norte)=22Iniciar sesión2norte>22Iniciar sesión2norte-1=2norte/ /2.
norte=2metro+1-1
T(2norte)=k=0 0metrot=2k2k+1-122k=k=0 0metro22k+k=Θ(22metro+metro),F(2norte)=22metro.
T(2norte)=Θ(F(2norte)).

Hay un teorema más general, Akra-Bazzi, en el que la condición de regularidad se reemplaza por una cantidad explícita que entra en el resultado.

Yuval Filmus
fuente
Perdón por reanudar esta vieja respuesta. ¿Podría aclarar por qué su función f viola la condición de regularidad?
Maiaux
Sometimes f(n/2)=f(n).
Yuval Filmus