Analizis algoritmos

Análisis de Algoritmos

Introducción

En Matemáticas y ciencia de la computación, un Algoritmo es un método efectivo

para la resolución de problemas, expresado como un conjunto de instrucciones y

reglas finitas pre escritas y bien definidas. Podemos usar más o menos lenguaje

formal tales como lenguaje natural,pseudocódigo o lenguajes de programación

como java, para expresar los algoritmos.

Por ejemplo si queremos calcular la sumatoria de los primeros N enteros

comenzamos con un valor resultado de 0 a continuación un bucle de 1 hasta N y

para cada valor de i agregamos i al resultado.

Estamos acostumbrado a tratar con algoritmos en nuestras vidas, si queremos

buscar una palabra en un diccionario, normalmente abrimos el diccionario por la

parte de enmedio. después buscamos nuevamente en la primera o segunda parte

dependiendo del orden alfabético, y así sucesivamente, o podemos mirar todas las

páginas en orden hasta encontrar la página que contiene nuestra palabra que

obviamente es menos eficiente.

En matemáticas podemos usar 2 métodos para calcular una lista de números primos

(Cualquier número que solo puede ser dividido por 1 y por si mismo) que son

menores a N: podemos iterar sobre los números impares o podemos usar la más

compleja pero más eficientes criba de Eratóstenes. La siguiente lista de pasos

describe el algoritmo de eratóstenes.

Rendimiento contra memoria:

Aunque el espacio de memoria (o espacio en disco si por ejemplo hablamos de una base de datos) es un recurso casi ilimitado en el cómputo moderno, esto puede todavía un problema para algunos algoritmos. Por ejemplo un algoritmo para una computadora que juega ajedrez debería necesitar almacenar todos los posibles movimientos que se han estudiado.

Algunas veces el mismo problema puede ser resuelto por un algoritmo que condiciona el rendimiento y un algoritmo que condiciona el espacio en memoria. Por ejemplo el algoritmo de Criba de Eratóstenes guarda el rendimiento, pero este necesita guardar un carácter booleano, que tiene un tamaño que es múltiplo del tamaño del problema, mientras el otro algoritmo necesita almacenamiento extra.

De otra manera el incremento del rendimiento mediante el uso de más memoria es para cambiar datos de forma en que son mostrados. Por ejemplo para regresar a un diccionario debemos redistribuir las letras y usar la función para calcular el número de página donde está dicha palabra, de esta forma encontramos que el tiempo debe ser constante, cualquier tamaño del diccionario, pero espacio de memoria (el número de página en el diccionario) crecerá considerablemente.

Como ejemplo, podríamos usar la siguiente función: Asignamos el valor a cada letra (A=0, B=1… Z=25) y y usamos las primeras tres letras por otras palabras (L1, L2 y L3), entonces el número de páginas deberían ser:

Este algoritmo es muy rápido, pero el almacenamiento es realmente importante tal diccionario debería tener 263 = 17576 páginas.

Análisis asintótica

Al analizar algoritmos, utilizamos notaciones asintóticas para mostrar de una manera matemática de cómo las escalas de consumo de recursos con el tamaño de entrada. El objetivo del análisis asintótica es centrarse en la forma de la curva de la función, y para definir las funciones de lo más simple posible que limitan o bien como una cota (gran O) superior, como un límite inferior (grande Omega), y como ambos (grande Theta). En este capítulo, nos centraremos en los límites de límite superior, y acaba de mencionar límites inferior consolidados.

Límite de cota superior gran O

Hemos visto en los ejemplos anteriores cómo la eficiencia

...