Bueno, no puede sin saber que T (n-1) se convierte en cero para algún valor bajo y todos los valores más bajos, preferiblemente al definir n como los números naturales. Entonces, digamos que sabes que T (1) = O (n). Entonces T (2) = 2 (O (n) + O (n)) = 4O (n), T (3) = 3 (4O (n) + O (n)) = 15O (n), T (4 ) = 4 (15O (n) + O (n)) = 64O (n), T (5) = 5 (64O (n) + O (n)) = 325O (n). Aquí el factor de O (n) está creciendo, por lo que la complejidad será mayor que O (n), y está creciendo rápidamente. Necesita calcular la expresión para ese factor, en términos de n, y determinar cuál es el factor dominante en ese momento. ¿Cuál es la función de n tal que f (1) = 1, f (2) = 4, f (3) = 15, f (4) = 64, f (5) = 325, y así sucesivamente? Sea lo que sea, T (n) = f (n) O (n), y si el término dominante de f (n) es una potencia de n, digamos que es n ^ x, T (n) = O (n ^ ( x + 1)). Si el término dominante no es una potencia de n, entonces necesita ver si dominaría n, en cuyo caso el término dominante de f (n) es el orden de todo.
Entonces, lo que te queda es resolver f (n) donde f (1) = 1 yf (n) = n (f (n-1) +1) (o equivalentemente f (n + 1) = (n +1) (f (n) +1)). Si no puede resolver eso analíticamente, entonces puede encontrar una solución candidata que parezca que funciona, y probarla usando la prueba por inducción (creo).
Siempre es difícil encontrar una expresión no recursiva para una función recursiva, y no siempre es posible. Solo mira la secuencia de Fibonacci, después de todo. Sin embargo, técnicamente no necesita una solución completa si puede demostrar cuál sería el factor dominante. Dependiendo de los criterios para la tarea, puede que esté bien graficarla y comparar la gráfica con varias funciones de n para ver cómo aumenta. Sin embargo, definitivamente miraría más allá de los poderes, exponentes y logaritmos.
- ¿Cómo encuentra Google Play las subcadenas más populares en un conjunto de revisiones?
- ¿Cuál será el algoritmo de rotación correcto en C?
- ¿Utiliza el cerebro el algoritmo de propagación hacia atrás dado cómo se conectan las sinapsis secuencialmente?
- ¿Cuáles son algunas aplicaciones prácticas del sistema binario?
- ¿Cómo podemos demostrar que cada matriz 1D tiene un pico o que cualquier matriz 1D siempre tiene un pico?
