Inicio > Java, Programacion, python > Análisis de algoritmos

Análisis de algoritmos

Imagen alojada en imaXenes.comEstoy leyendo sobre este tema porque la semana que viene tenemos el primer parcial de “Diseño e Implementación de Estructuras de Datos”, y es una de las unidades que comprende el examen, ésta junto a la de Recursión son las más interesantes, y útiles a la hora de llevar a cabo la programación.

En que consta este paradigmático tema?.
Cuando ejecutamos un programa, sobre una cantidad de datos debemos estar seguros de que el programa termina en un tiempo razonable, independientemente de la metodología empleada ( POO, Lógica, Procedural, etc.), y del lenguaje utilizado ( Python, Java, C++, etc.). Para ir decubriendo esto tenemos que en primera instancia conocer qué es un algoritmo.
Un algoritmo es un conjunto de instrucciones claramente especificadas que el ordenador debe seguir para resolver un problema, en un tiempo finito.

El análisis de algoritmos es el proceso que empleamos para determinar la cantidad de recursos (tiempo, espacio, etc.), necesarios para la ejecución de un algoritmo en particular. Siendo el tiempo de ejecución una función del tamaño de entrada, puede ser lineal, cuadrática, cúbica o logarítmica. El valor exacto de esta función dependerá de más factores, tales como la velocidad de la máquina, la calidad del compilador, y en alguno casos la calidad del programa.Lo que nosotros vamos a tratar de medir es el índice de crecimiento de éstas funciones.
De las funciones que mencionamos, la lineal representa el algoritmo más eficiente. Por esta razón trataremos que nuestros algoritmos según sea el caso se comporten como una función lineal.

Incluso los trucos de programación más inteligentes no pueden hacer rápido un algoritmo ineficiente. Por tanto, antes de perder el tiempo intenteando optimizar un código, debemos tratar optimizar el algoritmo.

Hay muchos algoritmos radicalmente diferentes ( en términos de eficiencia), que pueden ser utilizados para resolver distintos problemas. Podemos decir que en primera medida, tratamos de utilizar el algoritmos de fuerza bruta que es el más simple de implementar, pero también el menos eficiente.

Supongamos el siguiente ejemplo:
Dado un vector A con n enteros, hallar el mínimo valor de A
¿Cómo lo resolvemos?.
Opción 1:
def minimo_1(A):
....min = A[0]
....for i in vector:
........if(min < i):
............min = i
....return m

Opción 2:
def minimo_1(A):
....A.sort()
....return A[0]

Cuál es más complejo?, por qué?
Para responder adecuadamente esto tenemos que tener en cuenta los Órdenes de Complejidad, y en particular nosotros vemos Reglas generales para la notación O, ésta notación se puede usar para clasificar las funciones de acuerdo a la tasa de crecimiento. Podemos decir que la opción uno es O(N), “del orden N”, decimos ésto porque en el peor caso el mínimo valor se encontrará en el último lugar.
Ahora se preguntarán que si el arreglo A, crece en gran tamaño, nos convendría hacer que nuestro algorítmo se comporte en vez de linealmente, logarítmicamente. Yo les diría que si, pero en éste ejemplo en particular el arreglo – en principio viene desordenado- y por eso una Búsqueda Binaria ó Dicotómica no nos serviria. Tendríamos que estudiar si nos conviene ordenar y buscar ó simplemente buscar linealmente. Pero el mejor comportamiento para ordenar (si no se aprovecha la estructura de las claves) es O(n log n). Los algoritmos más simples son cuadráticos, es decir O(n²). Los algoritmos que aprovechan la estructura de las claves de ordenamiento (p. ej. bucket sort) pueden ordenar en O(kn) donde k es el tamaño del espacio de claves. Como dicho tamaño es conocido a priori, se puede decir que estos algoritmos tienen un desempeño lineal, es decir O(n).
Que es lo que opinan?.

La regla más importante es:
“El tiempo de ejecucion de un bucle es como mucho el tiempo de ejecución de las instrucciones dentro del bucle (incluyendo los test) multiplicado por el número de iteraciones”

Una vez que hemos efectuado el análisis de un algoritmo, queremos ver si es correcto y tan bueno como sea posible. Una forma de hacerlo es implementar el programa y ver si el tiempo de ejecución observado empíricamente se ajusta con el tiempo de predicho por el análisis.

Para terminar mi resumen, quiero aclarar que esto es una herramienta más, es muy efectiva, pero es importante conocer sus limitaciones. No es apropiado para pequeñas cantidades de datos, para ésto utilizamos el algoritmo más simple.

Es un tema que presta a la discución, sanamente no?. Pero se pueden debatir distintas metodologías para implementar sobre un mismo problema.

Referencias:
Análisis de Algoritmos
Tutorial
Algoritmos de Ordenamientos

Categorías:Java, Programacion, python
  1. No mamen
    septiembre 3, 2008 a las 5:12 am

    No le entiendo ni verga

  2. lecdmx
    octubre 4, 2008 a las 9:37 pm

    Interesante, yo estoy mas o menos en el mismo proceso que tú.

    Igual acabo de ver estos temas, y si son algunos enredos.

    Saludos

  3. ISA
    noviembre 8, 2008 a las 8:20 pm

    ya tampoco le entiendo ni !DAMIER!!!

  1. No trackbacks yet.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: