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

...