25-06-2014

1

Complejidad de Algoritmos

¿Cuándo proporciona un algoritmo una solución SATISFACTORIA a un problema?

Primero, debe producir siempre la respuesta correcta. Segundo, deberá ser eficiente.

¿Cómo se puede analizar la eficiencia de los algoritmos?

Una medida de eficiencia es el tiempo que requiere un ordenador para resolver un

problema utilizando un algoritmo para valores de entrada de un tamaño específico. Una segunda

medida es la cantidad de memoria que se necesita de nuevo para valores de entrada de un tamaño

dado. Una tercera medida sería estabilidad: un ordenamiento estable mantiene el orden relativo que

tenían originalmente los elementos con claves iguales.

Un análisis del tiempo requerido para resolver un problema de un tamaño particular está

relacionado con la complejidad en tiempo del algoritmo y un análisis de la memoria de ordenador

requerida involucra la complejidad en espacio del algoritmo. Obviamente, es importante saber si un

algoritmo producirá su respuesta en un milisegundo, en un minuto o en un millón de años y de manera

similar debemos tener suficiente memoria disponible para poder resolver el problema.

25-06-2014

2

Las consideraciones sobre complejidad en espacio están ligadas a las estructuras de

datos usadas en la implementación del algoritmo.

La complejidad en el tiempo de un algoritmo se puede expresar en términos del número

de operaciones que realiza el algoritmo cuando los datos de entrada tienen un tamaño particular.

(comparación de enteros, sumas, multiplicaciones, etc.)

La complejidad se describe en términos del número de operaciones requeridas en lugar del

tiempo de cálculo real, debido a que distintos ordenadores necesitan tiempos diferentes para realizar

las mismas operaciones básicas. Cada algoritmo se comporta de modo diferente de acuerdo a cómo

se le entregue la información; por eso es conveniente estudiar su comportamiento en casos extremos,

como cuando los datos están prácticamente ordenados o muy desordenados.

Complejidad del peor caso.- Por comportamiento de un algoritmo en el peor caso entendemos el

mayor número de operaciones que hace falta para resolver el problema dad utilizando el algoritmo

para unos datos de entrada de un determinado tamaño. Los análisis del peor caso nos dicen cuántas

operaciones tienen que realizar los algoritmos para garantizar que producirán una solución.

Complejidad del caso promedio.- En este tipo de análisis de complejidad se busca el número

promedio de operaciones realizadas para solucionar un problema considerando todas las posibles

entradas de un tamaño determinado. El análisis de la complejidad del caso promedio es

generalmente mucho más complicado que el análisis del peor caso.

25-06-2014

3

La complejidad del algoritmo se denota según la notación Big-O.

Las expresiones Big-O no tienen constantes o términos de orden bajo. Esto se debe a

que cuando N es muy grande, las constantes y los términos mas bajos no existen (un método

constante será más rápido que uno lineal y este será más rápido que uno cuadrático).

Por ejemplo, O(n) significa que el algoritmo tiene una complejidad lineal. En otras

palabras, toma 10 veces más tiempo en operar un set de 100 datos que en hacerlo con un set de 10

items. Si la complejidad fuera O(n2) entonces tomaría 100 veces más tiempo en operar 100 items

que en hacerlo con 10.

Complejidad Terminología

O(1) Complejidad constante

O(log n) Complejidad logarítmica

O(n) Complejidad lineal

O(n log n) Complejidad n log n

O(n^b) Complejidad polinómica

O(b^n) Complejidad exponencial

O(n!) Complejidad factorial

25-06-2014

4

Problemas Tratables, Intratables y NP-completos

Clase P.- Los algoritmos de complejidad polinómica se dice que son tratables en el sentido

de que suelen ser abordables en la práctica. Los problemas para los que se conocen algoritmos con

esta complejidad se dice que forman la clase P. Aquellos problemas para los que la mejor solución

que se conoce es de complejidad superior a la polinómica, se dice que son problemas intratables.

Clase NP.- Algunos de estos problemas intratables pueden caracterizarse por el curioso

hecho de que puede aplicarse un algoritmo polinómico para comprobar si una posible solución es

válida o no. Esta característica lleva a un método de resolución no determinista consistente en aplicar

heurísticos para obtener soluciones hipotéticas que se van desestimando (o aceptando) a ritmo

polinómico. Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de

polinómicos).

Clase NP-completos.- Se conoce una amplia variedad de problemas de tipo NP, de los

cuales destacan algunos de ellos de extrema complejidad. Gráficamente podemos decir que algunos

problemas se hayan en la "frontera externa" de la clase NP. Son problemas NP, y son los peores

problemas posibles de clase NP. Estos problemas se caracterizan por ser todos "iguales" en el

sentido de que si se descubriera una solución P para alguno de ellos, esta solución sería fácilmente

aplicable a todos ellos. Actualmente hay un premio de prestigio equivalente al Nobel reservado para el

que descubra semejante solución.

25-06-2014

5

El algoritmo requiere menos de O(n²) comparaciones y cambios en el pero caso. Aunque es fácil

desarrollar intuitivamente el sentido de cómo funciona el algoritmo, es bastante difícil analizar su

tiempo de ejecución pero los estimados difieren entre O(nlog2n) a O(n1.5) dependiendo de los

detalles de implementación

Dependiendo en la elección de la secuencia de saltos, Shell sort a probado tener un tiempo de

ejecución en el peor caso igual a O(n2), O(n3/2), O(n4/3) o O(nlog2n) o posiblemente mejores

tiempos de ejecución aún no probados. La existencia de una implementación que tenga una

complejidad O(nlogn) en el peor caso para el Shell sort aún se mantiene como una pregunta

abierta a la investigación.

El tamaño del set de datos usado tiene un impacto significativo en la eficiencia del algoritmo.

Algunas implementaciones de este algoritmo tienen una función que permite calcular el tamaño

óptimo del set de datos para un array determinado.

La secuencia de salto que fue sugerida inicialmente por Donald Shell fue comenzar con N/2 y

posteriormente disminuir a la mitad el salto hasta que llegue a 1. Esta secuencia provee una

mejora de desempeño sobre los algoritmos cuadráticos como el método por inserción pero puede

ser cambiada levemente para disminuir aún mas el tiempo de ejecución en el peor y el caso

promedio.