16/09/2019, 01:55:48 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Complejidad de algoritmos  (Leído 3509 veces)
0 Usuarios y 1 Visitante están viendo este tema.
batu
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 6


Ver Perfil
« : 08/05/2009, 11:54:55 pm »

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
En línea
mario
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.298



Ver Perfil
« Respuesta #1 : 09/05/2009, 12:02:15 am »

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.
En línea
malpas
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 17



Ver Perfil
« Respuesta #2 : 09/05/2009, 12:03:15 pm »

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

[texx]T(n) = n[/texx]

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:

[texx]c/2, c/2/2, c/2/2/2,\ldots,\frac{c}{2^k}[/texx]

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:

[texx]k = \log_2{c}[/texx]


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:

[texx]T = 3 *  \log{n}[/texx]

Finalmente tenemos que el tiempo total es:

[texx]T(n) = n + 3\log{n}[/texx]

Puedes hallar la complejidad buscando una sucesión que tenga el mismo orden que T(n).  Si cojemos como sucesión:

[texx]a_n = n[/texx]

Vemos que:

[texx]\displaystyle\lim_{x \to{+}\infty}{\frac{n + 3\log{n}}{n}} = 1[/texx]

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

[texx]F(n) = cT(n)[/texx]

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.

En línea
batu
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Chile Chile

Mensajes: 6


Ver Perfil
« Respuesta #3 : 09/05/2009, 10:08:05 pm »

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
En línea
topo23
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Argentina Argentina

Mensajes: 940


Ver Perfil
« Respuesta #4 : 10/05/2009, 11:39:22 am »

El ciclo while tiene orden [texx]\log i[/texx], el ciclo for ejecuta el while n veces.

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

En línea

.
malpas
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 17



Ver Perfil
« Respuesta #5 : 10/05/2009, 02:38:29 pm »

Hola batu.


El ciclo while tiene orden [texx]\log i[/texx], el ciclo for ejecuta el while n veces.

Luego el orden sera [texx]\log 2 + \log 3 + \cdots + \log n=O(n\log n)[/texx] 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.
En línea
topo23
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Argentina Argentina

Mensajes: 940


Ver Perfil
« Respuesta #6 : 10/05/2009, 03:06:18 pm »

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().
En línea

.
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!