Tipos de algoritmos

Clasificación de algoritmos * Algoritmo determinista: en cada paso del algoritmo se determina de forma única el siguiente paso. * Algoritmo no determinista: deben decidir en cada paso de la ejecución entre varias alternativas y agotarlas todas antes de encontrar la solución. Todo algoritmo tiene una serie de características, entre otras que requiere una serie de recursos, algo que es fundamentalconsiderar a la hora de implementarlos en una máquina. Estos recursos son principalmente: · El tiempo: período transcurrido entre el inicio y la finalización del algoritmo. · La memoria: la cantidad (la medida varía según la máquina) que necesita el algoritmo para su ejecución. Obviamente, la capacidad y el diseño de la máquina pueden afectar al diseño del algoritmo. En general, la mayoría de losproblemas tienen un parámetro de entrada que es el número de datos que hay que tratar, esto es, N. La cantidad de recursos del algoritmo es tratada como una función de N. De esta manera puede establecerse un tiempo de ejecución del algoritmo que suele ser proporcional a una de las siguientes funciones:
•

1 : Tiempo de ejecución constante. Significa que la mayoría de las instrucciones seejecutan una vez o muy pocas. logN : Tiempo de ejecución logarítmico. Se puede considerar como una gran constante. La base del logaritmo (en informática la más común es la base 2) cambia la constante, pero no demasiado. El programa es más lento cuanto más crezca N, pero es inapreciable, pues logN no se duplica hasta que N llegue a N2. N : Tiempo de ejecución lineal. Un caso en el que N valga 40, tardaráel doble que otro en que N valga 20. Un ejemplo sería un algoritmo que lee N números enteros y devuelve la media aritmética. N·logN : El tiempo de ejecución es N·logN. Es común encontrarlo en algoritmos como Quick Sort y otros del estilo divide y vencerás. Si N se duplica, el tiempo de ejecución es ligeramente mayor del doble. N2 : Tiempo de ejecución cuadrático. Suele ser habitual cuando setratan pares de elementos de datos, como por ejemplo un bucle anidado doble. Si N se duplica, el tiempo de ejecución aumenta cuatro veces. El peor caso de entrada del algoritmo Quick Sort se ejecuta en este tiempo. N3 : Tiempo de ejecución cúbico. Como ejemplo se puede dar el de un bucle anidado triple. Si N se duplica, el tiempo de ejecución se multiplica por ocho. 2N : Tiempo de ejecuciónexponencial. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. El problema de la mochila resuelto por un algoritmo de fuerza bruta -simple vuelta atrás- es un ejemplo. Si N se duplica, el tiempo de ejecución se eleva al cuadrado.

•

•

•

•

•

•

* Algoritmos polinomiales: aquellos que son proporcionales a Nk. Son en general factibles. * Algoritmosexponenciales: aquellos que son proporcionales a kN. En general son infactibles salvo un tamaño de entrada muy reducido. - Notación O-grande En general, el tiempo de ejecución es proporcional, esto es, multiplica por una constante a alguno de los tiempos de ejecución anteriormente propuestos, además de la suma de algunos términos más pequeños. Así, un algoritmo cuyo tiempo de ejecución sea T = 3N2 + 6N sepuede considerar proporcional a N2. En este caso se diría que el algoritmo es del orden de N2, y se escribe O(N2) Los grafos definidos por matriz de adyacencia ocupan un espacio O(N2), siendo N el número de vértices de éste. La notación O-grande ignora los factores constantes, es decir, ignora si se hace una mejor o peor implementación del algoritmo, además de ser independiente de los datos deentrada del algoritmo. Es decir, la utilidad de aplicar esta notación a un algoritmo es encontrar un límite superior del tiempo de ejecución, es decir, el peor caso. A veces ocurre que no hay que prestar demasiada atención a esto. Conviene diferenciar entre el peor caso y el esperado. Por ejemplo, el tiempo de ejecución del algoritmo Quick Sort es de O(N2). Sin embargo, en la práctica este caso no se...