Hola batu
El código del programa me mosquea porque el primer for lo único que hace ese ejecutarse n veces y dejar el valor de n en c. ¿Seguro que el bucle while no está dentro del for?
Pero bueno, supongo que será así.
Te digo cómo lo hago; es una manera algo bestia. Lo que hago es ir separando por partes el algoritmo en sí. Estas partes son los bucles y subprogramas. En este caso tenemos dos bucles que NO se ejecutan anidados, sino uno tras otro. Eso es importante.
Eso implica que el tiempo del algoritmo será tiempo_bucle 1 + tiempo_bucle 2
El primer bucle for se ejecuta n veces, ya que su contador crece de uno en uno. Luego se trata de una recta que va creciendo hasta n. El tiempo de ejecución sera
\( T(n) = n \)
En el segundo bucle podemos ver que, en principio, se ejecutará n veces, ya que c ha tomado el valor de n antes. Pero si te fijas, c se va dividiendo a sí misma entre dos, eso redce el número de iteracciones. También puedes ver que dentro del bucle hay tres instrucciones. Luego el T de cada iteracción será 3. Y el tiempo total en el que se ejecuta ese bucle será
3 * número iteracciones del bucle.
El número de iteracciones puedes determinarlo así:
El contador c decrece a este ritmo:
\( c/2, c/2/2, c/2/2/2,\ldots,\frac{c}{2^k} \)
Siendo k el número de iteracciones del bucle. Lo que nos interesa es ver cuánto es ese k, que determinará el tiempo del algoritmo.
Puede verse que el número de iteracciones es:
\( k = \log_2{c} \)
Hay que tener en cuenta que en el código que has puesto, c toma el valor de n. Luego se podría decir que el segundo bucle tiene de tiempo de ejecución:
\( T = 3 * \log{n} \)
Finalmente tenemos que el tiempo total es:
\( T(n) = n + 3\log{n} \)
Puedes hallar la complejidad buscando una sucesión que tenga el mismo orden que T(n). Si cojemos como sucesión:
\( a_n = n \)
Vemos que:
\( \displaystyle\lim_{x \to{+}\infty}{\frac{n + 3\log{n}}{n}} = 1 \)
Luego el algoritmo tiene un orden de complejidad O(n)
En realidad, la coplejidad se puede ver un poco a ojímetro. Teniendo en cuenta que el primer bucle se ejecuta n veces, la complejidad es O(n). El segundo bucle tiene una complejidad de O(log n) y como n crece mucho más rápido que log(n), pues la complejidad del algoritmo es O(n)
En la carrera apenas dimos complejidad de algoritmos. Lo cual puede que mi post no esté muy correcto, pero espero que al menos te sirva de guía.
De todas formas lo normal es calcular la complejidad. El tiempo T depende de muchos otros factores, como la capacidad de la máquina. De hecho se usa la complejidad ya que
\( F(n) = cT(n) \)
donde c es un aconstante y F(n) una función que acota asintóticamente a T(n). Se asegura que a partir de un n0 T(n) será acotado por f(n). De esta forma no tienes que preocuparte del harware dónde se ejecutará el algoritmo.
Saludos.
