Desafortunadamente, no existe un algoritmo para encontrar la complejidad temporal de un algoritmo dado. Ese es el corolario del famoso problema de detención que establece que no existe un algoritmo que responda si un programa terminará, funcionará infinitamente largo. Aparentemente, si pudiéramos encontrar la cantidad de operaciones que realiza el algoritmo, podríamos determinar si se detiene. (Eso es un poco duro, pero espero que tenga sentido)
Por lo tanto, debe encontrar un método específico de algoritmo cada vez. El ejemplo más simple si su programa es solo un montón de bucles for independientes anidados, como estos:
para i en rango (n):
para j en el rango (n):
imprimir (i + j)
- ¿Hay alguna razón para no usar el generador de números aleatorios estándar de C ++?
- ¿Cuál fue el primer juego de computadora en usar un generador de números aleatorios?
- ¿Cómo funcionan los algoritmos bayesianos para la identificación de spam?
- ¿Es posible implementar un montón dinámico paralelo?
- ¿Es posible crear un algoritmo de búsqueda mejor que el de Google?
La complejidad temporal de este código es [matemática] O (n ^ 2) [/ matemática] porque realiza la impresión exactamente [matemática] n ^ 2, [/ matemática] [matemática] n [/ matemática] veces en cada bucle para [ math] i [/ math] y como hay iteraciones [math] n [/ math] en el primer bucle, lo multiplicamos y obtenemos [math] n ^ 2 [/ math].
Eso fue bastante fácil, pero no es aplicable para la mayoría de las aplicaciones. La forma más general es encontrar biyección entre los estados del algoritmo y algunos objetos combinatorios que es fácil de contar. Permítanme tomar un ejemplo de impresión de todas las secuencias que contienen símbolos [matemáticos] n [/ matemáticos] del conjunto [matemático] \ {0,1 \} [/ matemático] de modo que no haya dos ceros consecutivos. Problemas como ese generalmente se resuelven con recursividad:
def resolver (actual, n):
si len (actual) == n:
imprimir (actual)
más:
resolver (actual + “1”, n)
si len (actual) == 0 o actual [len (actual) -1]! = ‘0’:
resolver (actual + “0”, n)
resolver (“”, n)
Entonces, comenzamos con una cadena vacía e intentamos agregar ceros y unos a su final, verificando si no aparecen dos ceros consecutivos. Existe una obvia biyección entre las operaciones de impresión y el conjunto [matemáticas] S_n = \ left \ {s_1 \ ldots s_n \ colon s_i \ in \ {0,1 \} \, \ land \, \ left (\ forall 1 \ le i <n \ colon (s_i \ neq 0) \ lor (s_ {i + 1} \ neq 0) \ right) \ right \} [/ math] porque ese es exactamente el conjunto de secuencias que queríamos imprimir. Entonces podemos notar que no hay más que [matemáticas] | S_n | \ cdot n [/ math] llamadas de resolución porque para cada impresión había exactamente [math] n [/ math] llamadas de resolución que formaban la secuencia que se imprimió.
Entonces, ¿qué es [matemáticas] | S_n | [/ matemáticas]? Puede notar que cada secuencia en [math] S_n [/ math] termina con 1 o con 10. Más que eso, [math] S_n = \ {s + 1 \ colon s \ en S_ {n-1} \} \ cup \ {s + 10 \ colon s \ en S_ {n-2} \} [/ math]. Entonces [matemáticas] | S_n | = | S_ {n-1} | + | S_ {n-2} | [/ math] y ahora podemos ver que [math] | S_n | = F_ {n + 1} [/ matemática] donde [matemática] F_0 = 0, F_1 = 1, F_i = F_ {i-1} + F_ {i-2} [/ matemática] – números de Fibonacci.
Por lo general, la complejidad del tiempo se escribe en la forma [math] O (\ alpha ^ {f (n)} \ cdot n ^ k) [/ math] donde [math] \ alpha [/ math] y [math] k [/ math ] son constantes. Aquí podemos usar la aproximación para los números de Fibonacci [matemática] F_n = O (\ phi ^ n) [/ matemática] donde [matemática] \ phi = {1 + \ sqrt {5} \ sobre 2} [/ matemática] y obtener el complejidad [matemática] O (\ phi ^ n \ cdot n) [/ matemática]
Bonificación: demuestre que en realidad este código hace que [math] F_2 + F_3 + \ ldots + F_ {n + 1} [/ math] resuelva llamadas que es [math] \ le F_ {n + 3} [/ math].
