Bueno, despues de tanto divagar... y de exprimir mi cerebro. He visto que hay una manera sencilla de obtener la complejidad operacional de un algoritmo
Lástima que sea a mano
. Expongo de manera simple en que consiste por si alguno les sirve:
1. Cada sentencia se asignación o de operación tiene complejidad O(1)
2. La complejidad de una sentencia IF depende si se está evaluando el mejor o el peor caso. Si es el peor se busca la parte que maximice la cantidad de complejidad. Por ejemplo si la parte THEN es 0(n) y la parte ELSE es 0(n^2). La complejidad total del IF es 0(n^2). Si se está evualando el mejor caso, la que minimice. La complejidad de la condición es 0(1) por lo cual se busca: max(0(1) //IF, 0() //sentencia) o min(0(1),0()).
3. De un grupo de secuencia de operaciones. Se debe buscar la suma de dichas complejidades. Es decir la que maximice (independiente si es el peor o mejor caso). Algo como: max(01(),02()) Donde 01 es la complejidad de la sentencia 1 y 2... bueno... de la 2.
4. Para un bucle: se debe multiplicar la cantidad de veces que se realiza por la complejidad de sus secuencias. Por ejemplo n * 0(n^2) = 0(n^3)
La regla básica a seguir es que se analice desde el interior hacia el exterior. Es decir, desde la sentencias mas internas a las externas.
Lo que debe entenderse desde el comienzo del análisis es que factor se analiza. Generalmente se impone a "n" como el tamaño de los vectores, de una matriz, de una cadena, etc. Si no puede determinarse el factor de estudio, deberá emplearse otro factor a estudiar.
Saludos,
¡Y yo que me mataba haciendo operaciones matemáticas...!