Analisis Algoritmico

Monografía sobre métodos de ordenamiento y análisis algorítmico

Javier A. Delgado A.
Comisión 1K4
Universidad Tecnológica Nacional
Facultad Regional Tucumán

Análisis Algorítmico
El análisis de algoritmos es una parte importante de la teoría de complejidad computacional, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problemacomputacional dado. Estas estimaciones resultan bastante útiles en la búsqueda de algoritmos eficientes. A la hora de realizar un análisis teórico de algoritmos es corriente calcular su complejidad en un sentido asintótico, es decir, para un tamaño bastante grande de entradas.
En las Ciencias de la Computación cuando se dice que un problema tiene solución, significa que existe un algoritmo susceptible deimplantarse en una computadora, capaz de producir la respuesta correcta para cualquier instancia del problema en cuestión. Para ciertos problemas es posible encontrar más de un algoritmo capaz de resolverlos, lo cual nos enfrenta al problema de escoger alguno de ellos. Es aquí donde entra en juego el análisis algorítmico que nos permite seleccionar el algoritmo más eficiente de entre todas lasopciones.

Orden de un algoritmo
La complejidad computacional estudia los costos de cómputo necesarios para resolver un problema; entendiéndose por costos los recursos de espacio de almacenamiento y de, principalmente, tiempo de cómputo. La complejidad temporal tiene que ver con el tiempo que tarda un programa para ejecutarse, la complejidad espacial estudia la cantidad de almacenamiento que esnecesario para una operación. Al analizar la complejidad de un algoritmo, el tiempo está expresado en términos de pasos de computación elementales (asignaciones, comparaciones, operaciones matemáticas básicas, etc.), por ejemplo, una operación de asignación ocupa una unidad de tiempo para ejecutarse, un ciclo ocupa el número de iteraciones en que está definido, etc.
Para cualquier tiempo deejecución que se desea determinar siempre se asumirá el peor de los casos.
Sea el siguiente ejemplo:
(1) suma = 0
(2) for (i=1; i<= n; i++)
(3) suma += i;
La instrucción (1) ocupa una unidad de tiempo.
La instrucción (3) ocupa dos unidades de tiempo, una para la suma y otra para la asignación, y es ejecutada N veces, por lo que ocupa 2N unidades de tiempo.
La instrucción (2) tiene involucradauna asignación que utiliza una unidad de tiempo, N+1 comparaciones y N incrementos, por lo que ocupa 2N+2 unidades de tiempo.
El tiempo total del algoritmo es T(N) = 1+2N+2+2N, esto es: T(N) = 4N + 3
De otra forma se podría ver como la existencia de tiempos para cada una de las posibles operaciones individuales, así: Ta – Tiempo de asignación, Tc – Tiempo de comparación, To – Tiempo deoperación, Ti – Tiempo de incremento.
La instrucción (1) posee Ta
La instrucción (3) posee un Ta y un To.
La instrucción (2) posee un Ta para i=1, Tc para i<=n, Ti para i++
Con base en estas valoraciones los tiempos serían así para el ciclo for las instrucciones internas se hacen la cantidad de veces que indique el ciclo, la instrucción interna tarda (Ta + To) el ciclo se realiza n-veces, lo cualindica un tiempo de n(Ta+To), ahora el ciclo realiza n veces el incremento de i++ es decir n(Ti) y las comparaciones son n+1 ya que el ciclo debe llegar hasta n+1 para que el ciclo pueda terminar, es por ello que es (n+1)Tc, y falta la asignación de i=1 es decir Ta, el tiempo total del algoritmo es : T(n) = n(Ta + To) + n(Ti) + (n+1)Tc + Ta + Ta, el total eliminando las agrupaciones es : n(Ta) +n(To) + n(Ti) + n(Tc) + Tc + Ta + Ta, factorizando n(Ta + To + Ti + Tc) + Tc + Ta + Ta, se aplica que cada uno de los tipos de operación tarda una unidad de tiempo, esta difiere en cada computador, por ello se toma general para este caso lo asumimos con valor 1, por ello sería el total final n(4) + 3, es decir el tiempo
T(n) = 4n + 3.
La pretensión de la segunda forma de evaluación es que se...