Autor Tema: Complejidad de algoritmos

0 Usuarios y 1 Visitante están viendo este tema.

09 Mayo, 2009, 04:54 am
Leído 4570 veces

batu

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 6
  • Karma: +0/-0
  • Sexo: Masculino
Hola
Primero que todo, disculpen si es la seccion equivocada para este tema.
Mi duda es como determinar la complejidad de una algoritmo, obteniendo el tiempo de ejecucion , y luego el orden .

Por ejemplo:

int c, x;  for(int i=0; i<n; i++){
c=i; while(c>0)
{ x = x % c;
c = c / 2;}
x = x + 2;}

He visto algunas formas pero no he podido comprender completamente como funciona este proceso.
Espero que puedan explicarme lo mas detallada posible por favor, ya que es algo totalmente nuevo para mi.

Gracias y
Saludos

09 Mayo, 2009, 05:02 am
Respuesta #1

mario

  • “El legato es el pastel y el pedal es la crema que hay en su interior” (Dinu Lipatti 1917-1950).
  • Administrador
  • Mensajes: 1,538
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Tienes un mensaje personal. Lo verás haciendo clic en el botón Mis mensajes.
Para que ese botón sea visible, tienes que haber entrado con tu nombre de usuario y contraseña.

09 Mayo, 2009, 05:03 pm
Respuesta #2

malpas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 17
  • Karma: +0/-0
  • Sexo: Masculino
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.


10 Mayo, 2009, 03:08 am
Respuesta #3

batu

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 6
  • Karma: +0/-0
  • Sexo: Masculino
Hola malpas

Toda la razón, el ciclo while va dentro del for, me falto una {.
En ese caso la solución que diste es igual?

Gracias

10 Mayo, 2009, 04:39 pm
Respuesta #4

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
El ciclo while tiene orden \( \log i \), el ciclo for ejecuta el while n veces.

Luego el orden sera \( \log 1 + \log 2 + \cdots + \log n=O(n\log n) \) sera el orden de ejecucion.

.

10 Mayo, 2009, 07:38 pm
Respuesta #5

malpas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 17
  • Karma: +0/-0
  • Sexo: Masculino
Hola batu.


El ciclo while tiene orden \( \log i \), el ciclo for ejecuta el while n veces.

Luego el orden sera \( \log 2 + \log 3 + \cdots + \log n=O(n\log n) \) sera el orden de ejecucion.



Pues ya te ha respondido topo23.

Como ves, ahora que los bucles son anidados, la complejidad es muy diferente: Es O(log n) -del bucle interno- N veces del for.

Saludos.

10 Mayo, 2009, 08:06 pm
Respuesta #6

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
Como ves, ahora que los bucles son anidados, la complejidad es muy diferente: Es O(log n) -del bucle interno- N veces del for.

Si la condicion de salida de los bucles fuera independientes entre si entonces es correcto multiplicar los ordenes. Pero en este caso la condicion de salida del while depende de la iteracion del ciclo for  y entonces lo que hay que hacer es la suma como escribi arriba, la diferencia entre ambas aproximaciones se ve mas cuando calculas T().
.