Anuncios Google

Para los que sepan programacion !

Como puedo saber el orden de un algoritimo? Es decir, si me dan un programa o algoritmo cualquiera, como puedo conocer su orden? Si es O(n) u O(n log n) y demas? Algun metodo por favor? es Urgente.


Canal de youtube        


Anuncios Google

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.

El orden se define, como el

El orden se define, como el número máximo de iteraciones que debe realizar el algoritmo.

 

Por ejemplo, para detectar un número uso el siguiente el algoritmo:

 

variable_control = 0:
 
mientras variable_control no sea igual a numero
 
        incrementar variable_control
 
end
 
devolver variable_control

 

Evidentemente, es una chapuza de algoritmo. Voy comparando todos los números a partir de cero hasta que llegue al número proporcionado. Su orden es n porque habrá que comparar tantos números como grande sea el número n.

Imagen de Carl's

Pero como saber todos los

Pero como saber todos los demas casos? Gracias por responder!

No hay ningún método

No hay ningún método genérico, habría que estudiar el caso en cuestión.

Imagen de joserc87

Si que hay un método "genérico"

Solo tienes que mirar el número de operaciones que hay que hacer en función de n. Empezando por lo básico, una operación sencilla (i=i+1; o x = y*z;) tendrían orden 1 puesto que son una operación.

Así el "algoritmo" (si se le puede llamar algoritmo)
 

tmp=sqrt(-4*a*c);
x1 = -b+tmp;
x2 = -b-tmp;
x1 = x1/2*a;
x2 = x2/2*a;

Tendría orden O(5) puesto que son 5 operaciones. Decimos que es de orden constante (son siempre 5 operaciones), luego es equivalente al orden O(1). Por lo que recuerdo, dos órdenes O1 y O2 son equivalentes si uno puede acotar superiormente al otro al multiplicarle una constante. Es decir, los ordenes O1 y O2 son equivalentes, si hay un A y un B tal que (asintóticamente) A*O1>O2 y O1<B*O2. Creo que eso ya lo sabes, así que no voy a entrar en detalles y explicarlo en profundidad. Si no te queda claro dilo y lo explico.

Otro algoritmo algo más complejo sería el algoritmo de burbuja (copy-paste de internet)

1. for (i=1; i<N; i++)
2.      for j=0 ; j<N - 1; j++)
3.           if (lista[j] > lista[j+1])
4.                temp = lista[j];
5.                lista[j] = lista[j+1];
6.                lista[j+1] = temp;

Para evaluar el orden nos tenemos que poner siempre en el peor de los casos. Pongamos que el if siempre es TRUE, luego las 3 instrucciones siempre se ejecutan. El número de instrucciones total serían 4*numero de ciclos del for interno * numero de ciclos del for externo. Ten en cuenta que digo 4 porque evaluar el if es una instrucción. El for externo se ejecutará desde 1 hasta N (luego son N-1 veces) y el interno desde 0 hasta N-1 (luego son N-1 veces tambien).

Así el orden del algoritmo sería O((N-1)*(N-1)*4)=O(4*N^2 - 8N + 4), o lo que es equivalente, O(n^2) (n cuadrado).

Ese es el método "genérico": mirar el número de instrucciones en función de n y luego reducir. Luego cuando tienes práctica, cuando ves un algoritmo tan tonto como el de arriba lo haces a ojo y dices "Dos bucles anidados? O(n^2) del tirón". Pero hay que tener cuidado con eso no nos vayamos a pasar de listos.

Saludos!


Be pointer my friend...

Dennis Ritchie. Padre de C y cocreador de UNIX.

R.I.P.

 

Imagen de Carl&#039;s

Mas excelente y completa

Mas excelente y completa respuesta no he podido obtener gracias joserc87! Me sirvio bastante! 

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.