No estoy seguro de cómo derivar las complejidades, pero puedo darle 2 ejemplos que tienen complejidades exponenciales:
1) Relación lineal con más de 1 términos en recursividad :
Por ejemplo, series de Fibonacci.
El algoritmo ingenuo y recursivo para calcular el enésimo término de fibonacci requiere el cálculo de los términos (N-1) th y (N-2) th.
Digamos, T (n) es el tiempo necesario para calcular el enésimo término. Ahora puedes decir,
T (n) = T (n-1) + T (n-2)
- Si un gráfico G contiene un puente, e, ¿es posible construir un árbol de expansión que no incluya este borde?
- ¿Qué representa un estado en términos de programación dinámica?
- ¿Cuál es el algoritmo de clasificación más rápido para una matriz de números grandes (hasta 1,000,000,000,000)?
- ¿Por qué es difícil estimar el tiempo de ejecución exacto de un algoritmo?
- ¿Cuáles son algunas de las implementaciones de cola (montón) de prioridad más rápida en C ++?
ahora, ¿cuál es la solución a la ecuación anterior? Podemos decir que x ^ n satisface la ecuación anterior, si,
x ^ n = x ^ (n-1) + x ^ (n-2)
x ^ 2 = x + 1 // descartando la solución trivial x = 0.
resolver para x da x = (1 + sqrt (5)) / 2. La otra raíz es negativa y el tiempo empleado no puede ser negativo, por lo que se descarta esa raíz.
Lo que dice que T (n) = {(1 + sqrt (5)) / 2} ^ n. Tenga en cuenta que este es un número> 1 y elevado a la potencia de n. ¡Esto es exponencial!
2) Permutaciones informáticas :
El algoritmo es dejar los elementos del primer término y el resto de permuta (N-1). Por cada permutación, se generan N permutaciones al colocar el primer término en todos los lugares posibles.
Si, T (n) es el tiempo necesario para calcular permutaciones para elementos (N), entonces podemos decir,
T (n) = nT (n-1)
La solución a la ecuación anterior es
T (n) = n!
Ahora, esto todavía no es exponencial, pero puedes demostrar que n! es de hecho equivalente a 2 ^ n. Ver aproximación de Stirling
Puede (de hecho debería) derivar todas las complejidades de la manera anterior.
Para darle otro ejemplo de la misma técnica (esto no es exponencial), puede intentar derivar O (N log N) de tipo de fusión:
Algo: Ordena los elementos primero (N / 2) y último (N / 2) por separado y luego se necesitan N comparaciones para obtener la matriz ordenada final.
Por lo tanto,
T (n) = T (n / 2) + T (n / 2) + n
T (n) = 2T (n / 2) + n.
La solución a lo anterior es:
T (n) = n log n
