Orden de algun algoritm

[ElPatoGarrido]

Hola, he estado aprendiendo las cosas basicas de programacion en C/C++, Pascal, etc... pero encuentro que hay algo que me cuesta mas y es la de ver el orden de un algoritmo, no de uno sencillo (si tampoco es tan dificil), pero por ejemplo si tengo el algoritmo para calcular la suecuencia de fibonacci de forma recursiva (y quiero calcular el orden de ese algoritmo) simplemente se me ocurre decir que es de O(n^2) por que fibonacci de n llamara recursivamente a la misma funcion 2 veces, despues estas 2 a otras 2, y asi sucesivamente lo que hara que se aproxime a 2^n, pero si me pidieran hacerlo de la forma matematica, o si me lo preguntaran en una prueba, no sabria como justificarlo, e imaginense si veo una funcion que se llama a si misma o a otras funciones por el argumento partido a la mitad etc... etc... etc... No tendria ni reverenda idea como calcular el orden de un algoritmo en casos mas complejos.

¿Alguien ha tenido el mismo problema, que puedo hacer?

Esa seria mi pregunta, gracias.

[ggomez91]

Es un tema un tanto complicado para explicarlo así pero haré lo que pueda.
Cuando hablas de complejidad n la n se refiere a los n datos que le das al algoritmo, entonces por ejemplo un for:

Código:

ejemplo = "ejemplo"
for (char c : ejemplo){
    print c;
}

por cada dato (cada char en "ejemplo") se hace una operacion, si se agraga un char ("ejemplo1"), se agrega una operación. En cambió si es un doble for:

Código:

ejemplo = "ejemplo"
for (char c : ejemplo){
    for (char b : ejemplo){
        print c+b;
    }
}

Ahí si agregar un char ("ejemplo1") realmente agregaste n operaciones mas, porque ahora el for de adentro se hara tambien para el char "1".

Para poder hacer este análisis de complejidad se suele hacer un procedimiento que consiste en sumar una constante A a cada operacion. Los ciclos se tratan como sumas (sumatorias) y pues la recursión es otra cosa que no podría explicar aquí.

Sé que quieres la explicación sobre el caso recursivo de fibonacci pero espero que esto te ayude un poco.

[alexg88]

Buenas,

El tema de la complejidad de los algoritmos es muy grande.

Te paso dos pdf que explican bastante bien algunas formas de calcular la complejidad de los algoritmos: http://www.lcc.uma.es/~av/Libro/CAP1.pdf

http://www.itescam.edu.mx/principal/...rsos/r4890.PDF

Un saludo.