Algoritmos

Algoritmos

I N T R O D U C C I O N

La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.

A efectos prácticos oingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parámetros, los más usuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parámetros están fijados por otras razones y se plantea la pregunta inversa: ¿cuál es el tamaño del mayor problema que puedo resolver en T segundos y/o conM bytes de memoria? En lo que sigue nos centraremos casi siempre en el parámetro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.

¿Qué es un Algoritmo?

Secuencia ordenada de pasos exentos de ambigüedad tal que, al llevarse a cabo con fidelidad, dará como resultado que se realiza la tarea para la que se ha diseñado en un tiempo finito.Un algoritmo nos permite tener una solución del problema para el que esté diseñado.

Concepto de complejidad de algoritmos: Un algoritmo será más eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.

La complejidad algorítmica representa la cantidad de recursos (temporales) que necesita un algoritmo para resolver unproblema y por tanto permite determinar la eficiencia de dicho algoritmo. Los criterios que se van a emplear para evaluar la complejidad algorítmica no proporcionan medidas absolutas sino medidas relativas al tamaño del problema. El tiempo empleado por un algoritmo se mide en pasos,

La medida del tiempo tiene que ser independiente:
De la máquina
Del lenguaje de programación
Del compiladorDe cualquier otro elemento hardware o software que influya en el análisis.
Para conseguir esta independencia una posible medida abstracta puede consistir en determinar cuantos pasos se efectúan al ejecutarse el algoritmo. El tiempo requerido por un algoritmo es función del tamaño de los datos. Por esta razón la complejidad temporal se expresa de la siguiente forma: T(n)
Dependiendo delproblema, el tamaño del dato representa cosas diferentes:
El número en sí
El número de dígitos o elementos que lo compone.
Otra característica importante es que no todos los datos, dentro de un problema, poseen la misma importancia de cara a la complejidad algorítmica.

La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:

Complejidad Temporal oTiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa.

Complejidad Espacial: Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo sesuma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.

Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa, intentaremoshallar respuestas en función de dicha N.

El concepto exacto que cuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lógica y...