¿Podemos decir que una relación de recurrencia es un tiempo de ejecución del algoritmo recursivo?

El tiempo de ejecución del algoritmo recursivo es una relación de recurrencia. En cuanto a la dirección opuesta por la que está preguntando … bueno, sí, uno puede argumentar que si tiene una relación de recurrencia (pero no una relación de recurrencia, porque ¿qué pasa si hay un valor negativo en alguna parte? ¿Qué quiere decir con diciendo “para la entrada n = 132, el algoritmo tarda un tiempo negativo en ejecutarse”?: D) entonces puede crear un algoritmo cuyo tiempo de ejecución está dado por esta relación. Pero es más como preguntar “¿podemos decir que un número entero es una cantidad de manzanas?” Bueno, sí, cualquier cantidad de manzanas es un número entero y para cualquier número entero (pero no negativo) hay una cantidad de manzanas igual a ese número , pero aun así personalmente no diría que esa oración es verdadera, por lo que lo mismo se aplica a su pregunta. Sin embargo, es más como una pregunta filosófica que matemática.

La relación de recurrencia le da el orden en que se generarán los datos. Por ejemplo, en el caso de la serie de Fibbonacci, f (n) = f (n-1) + f (n-2) es la relación de recurrencia para n mayor que 1. Por lo tanto, para calcular n necesitamos saber n-1 y n- 2 números Una vez que sepamos el tamaño y el rango del conjunto de datos en el que estamos operando, podemos adivinar cuál será el conjunto de datos del peor de los casos.

Una vez que sepamos esto, podemos estimar el peor tiempo que tomará nuestro algoritmo. Por lo tanto, en cierto modo, la relación de recurrencia no es el tiempo de ejecución por ejemplo, sino que ayuda a estimar el tiempo de ejecución del peor / mejor caso.