Análisis De Algoritmos

OBJETIVO: Conocer el término de análisis de algoritmos, dar a conocer fundamentalmente la eficiencia de uno o más algoritmos en cuanto el consumo de memoria y tiempo.

INTRODUCCIÓN

Generalmente utilizamos un ordenador porque necesitamos procesar gran cantidad de datos. Cuando ejecutamos un programa un gran cantidad de damos debemos estar seguros de que el programa termina dentro del plazo razonable. Esto es independiente, en la mayoría de los casos, del lenguaje de programación utilizado, e incluso de la metodología empleada.

Un algoritmo es un conjunto de instrucciones claramente especificadas que el ordenador debe de seguir para resolver un problema. Una vez que se ha dado un algoritmo para resolver un problema y se ha probado que es correcto, el siguiente paso es determinar la cantidad de recursos, tales como el tiempo y espacio que el algoritmo requiere para su aplicación.

DESARROLLO

5.1 ¿QUÈ ES EL ANALISIS DE ÁNALISIS DE ALGORITMO?

El tiempo necesario para ejecutar un algoritmo depende casi siempre de la cantidad de datos que el mismo debe procesar. Es esperar, por ejemplo, que ordenar diez mil elementos requiera más tiempo que ordenar diez. El tiempo de ejecución de un algoritmo de un algoritmo es, por lo tanto función de la entrada. El valor exacto de esta función del tamaño de entrada. El valor exacto de esta función depende de muchos factores tales como la velocidad ce la máquina, la calidad del compilador, y en algunos casos, de la calidad del programa.

5.2 EJEMPLOS DE TIEMPO DE EJECUCIÓN DE ALGORITMOS

ELEMENTOS MÍNIMOS DE UN VECTOR

Dado un vector de N elementos, encontrar el elemento más pequeño.

PUNTOS MÁS CERCANOS EN EL PLANO

Dados N puntos en un plano(es decir, en un sistema de coordenadas x-y), determinar si existen tres que se encuentran en línea recta.

PUNTOS COLINEALES EN EL PLANO

Dados N puntos en un plano (es decir, en un sistema de coordenadas x-y), determinar si existen tres que se encuentren en línea recta.

El problema del elemento mínimo es fundamental en computación. Puede ser el resultado de la siguiente manera:

Mantener una variable min que almacene el elemento mínimo.

Inicializar min al primer elemento.

Hacer un recorrido secuencial a del vector, actualizando min de forma adecuada.

El tiempo de ejecución de este algoritmo será lineal, es decir O(N), pues repetimos una cantidad fija de trabajo por cada elemento del vector. Un algoritmo lineal es todo lo bueno que podemos esperar. Esto es debido a que tenemos que examinar cada elemento del vector, un proceso que inodoramente requiere un tiempo lineal.

El problema del par de puntos más cercanos es un problema fundamental en las artes gráficas que podemos resolver de la siguiente manera:

Calcular la distancia entre cada par de puntos.

Conservar la mínima distancia.

Sin embargo éste es un cálculo costoso, ya que hay N(N-1)/2 pares de puntos. Por lo tanto. Hay aproximadamente N^2 pares de puntos. Examinar todos estos pares y calcular la distancia mínima entre ellos supondrá un tiempo cuadrático.

Existe un algoritmo mejorado que se ejecuta en tiempo O(N log N) que trabaja evitando el cálculo de todas las distancias. Existe además algoritmo del que se supone que tarda un tiempo O(N). Estos dos últimos algoritmos utilizan sutiles observaciones para proporcionar resultados de forma rápida, y están más allá del alcance de este texto.

El problema de los puntos colineales es importante en muchos algoritmos gráficos. Esto se debe a que la existencia de puntos colineales introduce un caso degenerado que requiere un tratamiento especializado.

5.3 EL PROBLEMA DE LA SUBSECUENCIA DE SUMA MÁXIMA

Dada la secuencia de enteros (posiblemente negativos) A1, A2…AN encontrar (e identificar la subsecuencia correspondiente) el valor máximo de ∑_(k=i)^j▒(A_K ) . Cuando todos los enteros son negativos entendernos que la subsecuencia de la suma máxima es la vacía, siendo suma cero.

Por ejemplo, la entrada {-2, 11, -4, 13, -5, 2}, la respuesta es 20. La misma corresponde a la subsecuencia que abarca los elementos del segundo al cuarto.

5.3.1 EL ALGORITMO O(N^2)OBVIO

El algoritmo más simple consiste en una búsqueda exhaustiva, o un algoritmo de fuerza bruta, tiene el mérito de ser extremamente simple, cuando menos complejo es un algoritmo, más probable es que se programe con corrección. Sin embargo, por lo general, los algoritmos de búsqueda exhaustiva no son tan eficientes como sería posible.

Se utiliza un razonamiento matemático para contar el número de veces que ciertas instrucciones son ejecutadas. No necesitamos hacer muchos cálculos precisos para producir una estimación O.

5.3.2 UN ALGORTMO MEJORADO O (N^2)

Cuando eliminamos un bucle anidado interior de un algoritmo, generalmente reducimos el tiempo de ejecución.

5.3.3 UN ALGORITMO LINEAL

Para pasar de un algoritmo cuadrático a un lineal, solamente eliminamos otro bucle conseguiremos un algoritmo lineal. El algoritmo es dedicado. Utiliza una habilidad observación para saltarse gran número de subsecuencia que no pueden ser la mejor.

5.4 REGLAS GENERALES DE PARA LA NOTACIÓN O

DEFINICIÓN:(O) T(N) es O (F(N)) si existen constantes positivas c y N0 tales que para N≥N0 se verifica T(N) ≤Cf(N).

DEFINICIÓN: (Ω) T(N) es Ω (F(N) si existen constantes positivas c y No tales que para N≥NO se verifica T(N) ≥NO se verifica T(N) ≥Cf(N).

DEFINICIÓN: () T(N) es  (F(N) si sólo si y sólo si T(N) es 0(F(N)) Y T(N) es Ω (F(N)).

DEFINICIÓN: (0) T(N) ES 0(F(N)) si sólo si T(N) es O (F) (N)) y T(N) no es  (F(N)).

5.5 LOGARITMOS

DEFINICIÓN: Para cualquier B, N >O, log N=K si BK = N

5.6.1 BÚSQUEDA BINARIA

La búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O (log(n)), coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen porque tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado está relacionada por una constante multiplicativa llamada constante oculta.

La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo.

...