Analisis de algoritmos

INTRODUCCION

Durante el desarrollo de esta unidad veremos lo que significado un algoritmo y los tipos de algoritmos que existen o en los cuales se clasifican.
El cómo será su complejidad, su aritmética y cuando seleccionar un algoritmo el cual cada uno de ellos nos mostrara como estará estructurado, saber cada uno de ellos así como podremos desarrollarlos fácilmente sin tener ningún problemapara saberlo aplicar.

ANALISIS DE ALGORITMOS

Para empezar a desarrollar este tema tendremos que definir antes que nada que es un algoritmo.
Un algoritmo es una secuencia finita u ordenada de pasos a seguir, los cuales tienen como función la solución de un problema que se nos presente. Los algoritmos están divididos en dos bloques según cual sea la función de este, entre los cualesencontramos:
• Algoritmo de ordenamiento:

Es un algoritmo que pone elementos de una lista o un vector en una secuencia 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 dedatos. Consiste en solucionar un problema booleano de existencia o no de un elemento determinado en un conjunto finito 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.

1.1 CONCEPTO COMPLEJIDADALGORITMOS

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 o ingenieriles, nos deben preocuparlos 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 con M bytes de memoria?
En loque sigue nos centramos casi siempre en el parámetro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.
Para cada problema determinaremos una medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N.
El concepto exacto que mide N depende de la naturaleza del problema.
Así, para un vector se sueleutilizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es más importante considerar el número de arcos, dependiendo del tipo de problema a resolver), en un archivo se suele usar el número de registros, etc. Es imposible dar una regla general, pues cada problema tiene su propia lógica de coste.
Tiempo de Ejecución
Unamedida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N).
Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción.
Así, un trozo sencillo de programa como:
S1; for (int i= 0; i < N; i++)S2;
Requiere:
T(N)= t1 + t2*N
Siendo t1 el tiempo que lleve ejecutar la serie “S1” de sentencias, y t2 el que lleve la serie “S2”.
Prácticamente todos los programas reales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten.
Esto hace que más que un valor T(N) debamos hablar de un rango de valores...