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.
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.
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)
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.
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:
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.
Mi creacciónes particulares:
http://www.scenebeta.com/noticia/la-serpiente
http://www.scenebeta.com/node/22535
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.
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)
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)
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!
Dennis Ritchie. Padre de C y cocreador de UNIX.
R.I.P.
Mas excelente y completa
Mas excelente y completa respuesta no he podido obtener gracias joserc87! Me sirvio bastante!