Ensayo de estructura de datos

Introducción

¿Cómo comparar dos algoritmos para resolver un mismo problema en términos de eficiencia?

En la computación los algoritmos son sumamente importantes, ya que gracias ala elaboración de los mismos podemos resolver diferentes tipos de problemas haciendo uso de las computadoras, requiere por una parte un algoritmo o método de resolución y por otra un programa o codificación delalgoritmo. Ambos componentes tienen importancia; pero la del algoritmo es absolutamente indispensable; sabemos que un algoritmo es una secuencia de pasos para resolver un problema. Veremos la relación algorítmica con los tiempos de ejecución y espacio, su complejidad, la selección de los tipos de algoritmos y cual es la importancia de tener un algoritmo eficiente.

Relación entre complejidad algorítmicay tiempos de ejecución

En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo es una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final, obteniendo una solución. Los algoritmos son objeto de estudio de laalgoritmia.
En la vida cotidiana se emplean algoritmos en multitud de ocasiones para resolver diversos problemas. Algunos ejemplos se encuentran en los instructivos (manuales de usuario), los cuales muestran algoritmos para usar el aparato en cuestión o inclusive en las instrucciones que recibe un trabajador por parte de su patrón. También existen ejemplos de índole matemática, como el algoritmo de ladivisión para calcular el cociente de dos números, el algoritmo de Euclides para calcular el máximo común divisor de dos enteros positivos, o el método de Gauss para resolver un Sistema lineal de ecuaciones.

Tenemos distintos tipos de algoritmos y aquí un ejemplo de algoritmos según su función:

• Algoritmo de ordenamiento
Es un algoritmo que pone elementos de una lista o un vector en unasecuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación o reordenamiento de la entrada que satisfaga la relación de orden dada.

• Algoritmo de búsqueda
Es aquel que está diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en solucionar un problema booleano de existencia o no de un elemento determinado en un conjuntofinito de elementos, es decir al finalizar el algoritmo este debe decir si el elemento en cuestión existe o no en ese conjunto (si pertenece o no a él), además, en caso de existir, el algoritmo podría proporcionar la localización del elemento dentro del conjunto.

La complejidad del algoritmo, que no tiene que ver con dificultad, sino con rendimiento. Es una función independiente de laimplementación, que da el tiempo y/o el espacio utilizado por el algoritmo en función del tamaño de entrada. Debemos tener en cuenta que cada algoritmo guarda una estrecha relación con una estructura de datos. Como programadores no siempre utilizamos el algoritmo más eficiente ya que la elección de la estructura de datos se apega a varias cuestiones tales como que tipo de datos estamos administrando y lafrecuencia con que se realizan diferentes operaciones. Un programa pude estar compuesto de gran cantidad de código fuente detallado pero no por esto podemos decir que el programa es mas eficiente que uno que esta compuesto por menos cantidad de código, todo esta en la manipulación de tipo de datos que manejamos.

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

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

En pocas palabras nos estamos refiriendo al tiempo en que tardara un programa en realizar lo que se le esta pidiendo.

El tiempo de ejecución de un algoritmo se define como T(n), para describirlo mejor se realizara un ejemplo.
Ejemplo:
Num Línea | Potencia(real x, entero...