El teorema maestro nos permite calcular el tiempo de ejecución asintótico para algoritmos de divide y vencerás que dividen cada problema en subproblemas [matemáticos] a [/ matemáticos] donde cada subproblema es [matemático] b [/ matemático] veces más pequeño que el original problema. Además, en cada iteración, se realiza una cantidad adicional de trabajo igual a [math] f (n) [/ math].
Entonces nuestra recurrencia es: [matemáticas] T (n) = a \, T (n / b) + f (n) [/ matemáticas]
Para comprender esto intuitivamente, imagine la estructura de árbol de las llamadas recursivas, con todo el problema en la raíz, y sus subproblemas inmediatos como sus hijos, y así sucesivamente. Observe que [matemáticas] f (n) [/ matemáticas] es la cantidad de trabajo realizado en el primer nivel, [matemáticas] af (n / b) [/ matemáticas] es la cantidad de trabajo realizado en el segundo nivel, [matemáticas ] a ^ 2 f (n / b ^ 2) [/ math] es la cantidad de trabajo realizado en el tercer nivel, y así sucesivamente.
- ¿Puede C (lenguaje de programación) tratar con grandes números?
- ¿Por qué el hardware de gráficos solo representa triángulos?
- ¿Qué buscan las escuelas de posgrado en estadística / aprendizaje automático en Ph.D. ¿solicitantes?
- ¿Cómo es UMass para un estudiante universitario en ciencias de la computación para estudiantes interesados en IA? ¿Con qué otras universidades se compara?
- ¿Cuáles son los fundamentos matemáticos de la inteligencia artificial?
Las palabras en negrita a continuación resaltan la intuición. El resto es solo álgebra.
Hay tres casos:
Caso 1: [matemática] f (n) = O (n ^ c) [/ matemática] donde [matemática] c 1 [/ matemáticas].
Si [matemática] f (n) = O (n ^ c) [/ matemática], la cantidad de trabajo realizado en el i-ésimo nivel es [matemática] a ^ i O ((n / b ^ i) ^ c) [/ matemática], o [matemática] O ((a / b ^ c) ^ kn ^ c) [/ matemática]. Como [matemática] a / b ^ c> 1 [/ matemática], esto significa que la cantidad de trabajo realizado en cada nivel más allá del primero aumenta geométricamente o más rápido. Por lo tanto, aproximadamente una fracción constante del trabajo se realiza en el nivel más bajo . Hay aproximadamente [math] \ log_b n [/ math] niveles, por lo que el nivel más bajo tiene aproximadamente [math] a ^ {\ log_b n} = n ^ {\ log_b a} [/ math] nodos. Por lo tanto, el trabajo total realizado es sobre [matemáticas] f (1) n ^ {\ log_b a} = \ Theta (n ^ {\ log_b a}) [/ matemáticas].
Caso 2: [matemática] f (n) = \ Theta (n ^ c \ log ^ kn) [/ matemática] donde [matemática] c = \ log_b a [/ matemática]. Esto significa que [matemáticas] a / b ^ c = 1 [/ matemáticas]. Primero consideremos qué sucede si [math] k = 0 [/ math]. Entonces, la cantidad de trabajo realizado en cada nivel es [matemática] O ((a / b ^ c) ^ kn ^ c) = O (n ^ c) [/ matemática]; que es independiente del nivel . La cantidad de trabajo realizado en cada nivel es aproximadamente la misma . Entonces, el trabajo total es simplemente el número de niveles multiplicado por el trabajo realizado en el primer nivel , [matemáticas] T (n) = \ Theta (f (n) \ log_b n) = \ Theta (n ^ c \ log n) [ /mates].
Ahora, ¿qué pasa si [matemáticas] k> 0 [/ matemáticas]? Luego, la cantidad de trabajo realizado en el i-ésimo nivel se modifica ligeramente a [matemática] \ Theta (n ^ c \ log ^ k (n / b ^ i)) [/ matemática] por lo que ya no es realmente constante; cae alométricamente a medida que profundizas (es decir, como una ley de poder). Puede verificar aproximando la suma como una integral que la cantidad promedio de trabajo realizado por nivel es una fracción constante (constante wrt [matemática] n [/ matemática], es decir) de la cantidad de trabajo realizado en el primer nivel . Por lo tanto, el trabajo total es nuevamente [matemática] T (n) = \ Theta (f (n) \ log_b n) = \ Theta (n ^ c \ log ^ {k + 1} n) [/ math].
Caso 3: [matemática] f (n) = \ Omega (n ^ c) [/ matemática] donde [matemática] c> \ log_b a [/ matemática]; más una condición de regularidad adicional. Esto es equivalente a [matemáticas] a / b ^ c <1 [/ matemáticas]. Por el mismo razonamiento que en el caso 1, la cantidad de trabajo realizado en el nivel i es [matemática] \ Omega ((a / b ^ c) ^ kn ^ c) [/ matemática], por lo que la cantidad de trabajo realizado en cada el nivel disminuye geométricamente o más rápido a medida que baja. Por lo tanto, aproximadamente una fracción constante del trabajo se realiza en el nivel más alto . Por lo tanto, [math] T (n) = \ Theta (f (n)) [/ math].
La condición de regularidad garantiza que la cantidad de trabajo realizado en cada nivel realmente disminuya geométricamente, al prohibir las funciones de mal comportamiento [matemática] f [/ matemática] que oscilan enormemente para [matemática] n [/ matemática] arbitrariamente grande.
