Supongamos que un algoritmo tiene una relación de recurrencia en tiempo de ejecución:
para alguna constante . Suponga que es polinomial en , quizás cuadrático. Lo más probable es que sea exponencial en .g n f n
¿Cómo se podría analizar el tiempo de ejecución ( sería excelente)? El teorema maestro y el método más general de Akra-Bazzi no parecen aplicarse.
asymptotics
recurrence-relation
Austin Buchanan
fuente
fuente
Respuestas:
Un posible enfoque podría ser por analogía con las ecuaciones diferenciales. Deje . Aquí es un análogo discreto de la primera derivada de . Obtenemos la siguiente relación: El análogo continuo de esto es la ecuación diferencial o, si prefiere verla escrita de manera diferente: Esa es una ecuación diferencial.T′(n)=T(n)−T(n−1) T′(n) T(n)
Ahora podría intentar resolver la ecuación diferencial para la función continua , luego plantear la hipótesis de que una función similar será la solución a su relación de recurrencia original e intentar demostrar su hipótesis. Al menos, este es un enfoque general que podría seguir.t(x)
He olvidado todo lo que una vez supe sobre las ecuaciones diferenciales, por lo que no conozco la solución de esa ecuación diferencial, pero tal vez puedas resolverla revisando todas las técnicas para resolver ecuaciones diferenciales.
fuente