COMPLEJIDAD DE ALGORITMOS

Complejidad computacional y asintótica

Para resolver un problema suele ser habitual disponer de varios algoritmos. 

El objetivo es elegir el algoritmo más eficiente de ellos.

-Regla: La elección del algoritmo nunca debería afectar a la corrección de la solución ni a la claridad (evitar algoritmos incomprensibles).

-Excepción: A veces se eligen algoritmos aproximados o heurísticos porque la solución correcta resulta inmanejable. No alcanzan la solución óptima pero sí a una solución aceptable.

Para comparar algoritmos se puede utilizar una medida del grado de dificultad del algoritmo: la complejidad computacional.

COMPLEJIDAD COMPUTACIONAL

-Indica el esfuerzo que hay que realizar para aplicar un algoritmo y lo costoso que éste resulta.

Un algoritmo es más eficiente cuanto menos complejo sea.

La eficiencia suele medirse en términos de consumo de recursos:

–                   Espaciales: cantidad de memoria que un algoritmo consume o utiliza durante su ejecución à Complejidad espacial

–                   Temporales: tiempo que necesita el algoritmo para ejecutarseà Complejidad temporal

–                   Otros: utilización de CPU, utilización de periféricos, tiempo y coste de implementación...

Factores que influyen en la complejidad

–                   Tamaño del problema

–                   Naturaleza de los datos de entrada

–                   Recursos hardware y software

Principio de invarianza:

Dos implementaciones de un mismo algoritmo no diferirán más que en una constante multiplicativa.

Si f₁(n) y f₂(n) son los tiempos consumidos por dos implementaciones de un mismo algoritmo, se

verifica que:

$ c, d Î R,

f₁(n) £ c·f₂(n)

f₂(n) £ d·f₁(n)

COMPLEJIDAD ASINTÓTICA

Consiste en el cálculo de la complejidad temporal a priori de un algoritmo en función del tamaño del problema, n, prescindiendo de factores constantes multiplicativos y suponiendo valores de n muy grandes. No sirve para establecer el tiempo exacto de ejecución, sino que permite especificar una cota (inferior, superior o ambas) para el tiempo de ejecución de un algoritmo

La notación O

Existen diferentes notaciones para la complejidad asintótica. Una de ellas es la notación O, que permite especificar la cota superior de la ejecución de un algoritmo. La sentencia “f(n) es O(g(n))” significa que la tasa de crecimiento de f(n) no es mayor que la tasa de crecimiento de g(n). La notación “O” sirve para clasificar las funciones de acuerdo con su tasa de crecimiento.

O(1)	Constante	No depende del tamaño del problema	Eficiente
O(log n)	Logarítmica	Búsqueda binaria
O(n)	Lineal	Búsqueda lineal
O(n•log n)	Casi lineal	Quick-sort
O(n2)	Cuadrática	Algoritmo de la burbuja	Tratable
O(n3)	Cúbica	Producto de matrices
O(nk) k>3	Polinómica
O(kn) k>1	Exponencial	Algunos algoritmos de grafos	Intratable
O(n!)	Factorial

Cambios en el entorno HW o SW afectan a factores constantes (principio de invarianza) pero no al orden de complejidad O(f(n)). Hay que buscar algoritmos con el menor orden de complejidad. La eficiencia es un término relativo que depende del problema. El análisis de la eficiencia es asintótico à sólo es válido para tamaños de problema suficientemente grandes.
El análisis asintótico de algoritmos determina el tiempo de ejecución en notación “O”. Para realizar el análisis asintótico
– Buscar el número de operaciones primitivas ejecutadas en el peor de los casos como una función del tamaño de la entrada
– Expresar esta función con la notación “O”
Ejemplo:
– Se sabe que el algoritmo maximoArray ejecuta como mucho 7n - 1 operaciones primitivas
– Se dice que maximoArray “ejecuta en un tiempo O(n)”
Como se prescinde de los factores constantes y de los términos de orden menor, se puede hacer caso omiso de ellos al contar las operaciones primitivas