old_tutorials‎ > ‎

Algoritmia y Complejidad

Algoritmos


Un algoritmo es un conjunto ordenado y finito de operaciones que permite halla la solución de un problema. Si pensamos en programación de computadores, un algoritmo correctamente diseñado, junto con una representación adecuada de la información manejada, dará lugar a un programa que permite resolver el problema computacional planteado. De ahí lo acertado del título de una de las obras clásicas en el campo: "Algoritmos + Estructuras de Datos = Programas", por N. Wirth.

El diseño de algoritmos es todo un campo de estudio, ya que el avance en las ciencias de la computación ha alumbrado numerosas técnicas para dar solución a diferentes clases de problemas. Si deseas más información, existen infinidad de libros y cursos, aunque como referencia rápida puedes recurrir enlaces como este, o este otro.

Complejidad Computacional


Inherente al estudio de los algoritmos es el análisis de su complejidad. Obviamente, un algoritmo demanda una cierta cantidad de recursos computacionales. La complejidad algorítmica trata  de cuantificar esos recursos, por lo que mide la dificultad de resolución de un problema mediante un determinado método.

En la teoría de la complejidad computacional es común referirse a la cantidad de memoria utilizada y/o al tiempo de ejecución que demanda el algoritmo. Asimismo, suele estudiarse en función del caso mejor, caso medio y caso peor. Las medidas no suelen ser de carácter absoluto, sino que habitualmente se expresan en función del tamaño del problema, y son de carácter asintótico. 

En lo sucesivo vamos a designar mediante n el tamaño del problema, y vamos a abordar el estudio del tiempo de ejecución en el peor de los casos, para lo cual usaremos la notación O (o grande). Por ello, tendremos algoritmos, por ejemplo, de:
- O(1): el tiempo de ejecución del algoritmo es constante (se resuelve en un único paso básico).
- O(n): el tiempo de ejecución del algoritmo es lineal, y demanda n operaciones básicas.
- O(n^2): el tiempo de ejecución del algoritmo es cuadrático.
- O(log(n)): el tiempo de ejecución del algoritmo es logarítmico.

Hay numerosas referencias que puedes usar si te interesa el tema y te animo a buscarlas. No obstante, para hacernos una idea preliminar, vamos a jugar con un problema sencillo, donde simplemente veremos la influencia que tiene realizar un diseño correcto de una algoritmo o resolverlo de la primera forma que se nos ocurra.

Ejercicio:


Pensemos en la búsqueda de un elemento en un array ordenado de valores reales de n elementos (el tamaño de nuestro problema es n). 
  • Pensemos en un procedimiento sencillo de búsqueda bruta como es una búsqueda secuencial: empezando por el primer elemento vamos comparando el contenido de cada posición del array con el elemento buscado. Si lo hemos encontrado listo y si no pasamos a la siguiente posición. Así hasta encontrar el elemento o llegar al límite del array. Obviamente, si el tamaño del array es de n elementos, tendremos que dar a lo sumo n pasos si elemento que buscamos no está en el array (peor caso). Por ello, en el peor de los casos la complejidad de nuestro algoritmo es O(n).
  • Pensemos ahora en un método de búsqueda algo más elaborado, como es la búsqueda dicotómica (busca información de cómo es este método). En el peor de los casos, mediante este algoritmo tendremos que realizar log2(n) pasos, por lo que el tiempo de ejecución se reducirá respecto al caso anterior a O(log2(n)).
Lo que te planteo es lo siguiente:
  • Crea una clase Array, que tenga como miembro un vector de valores reales de un tamaño indeterminado. La creación del vector se hará en la construcción del objeto pasándole el tamaño deseado. El contenido del array se inicializará como desees oportuno, con la única restricción de que ha de estar ordenado.
  • Implementar dos métodos de la clase, que realicen respectivamente una búsqueda secuencial y una búsqueda dicotómica.
  • En el programa principal (main), crear un objeto Array de una tamaño grande (100000 elementos, por ejemplo), y ver el tiempo de ejecución de realizar una búsqueda lineal y una dicotómica de un elemento no presente en el mismo.

Comments