Bachiller

Algoritmos de Búsqueda y Ordenación.

Rosalía Laza Fidalgo. Departamento de Informática. Universidad de Vigo

Complejidad
¿ Cómo podemos medir y comparar algoritmos, si estos se ejecutan a distintas velocidades y requieren diferentes cantidades de espacio según en qué ordenador se ejecuten, y con qué lenguaje de programación (o compilador) hayan sido implementados? Con la simple recogida delos tiempos de ejecución de los algoritmos indudablemente no.
Tamaño del array n 125 250 500 1000 2000 Ordenador A (ms) 12.5 Ordenador B (ms) 2.8

49.3

11.0

195.8

43.4

780.3

172.9

3114.9

690.5

Complejidad
3500 Tiempo de Ejecución 3000 2500 2000 1500 1000 500 0 125 250 500 T am añ o 1000 2000 f 1(n) f 2(n)

f1(n) = 0,0007772n2+0,00305n+0,001f2(n)=0,0001724n2+0,00400n+0,100

Independientemente de la máquina, el lenguaje de programación o el compilador que se haya utilizado para la ejecución del algoritmo A, el tiempo de ejecución que consume dicho algoritmo SIEMPRE dará lugar a una función cuadrática del tamaño del array que trate. Es decir, la forma de la curva será la misma.

Notación O.
Los tiempos de ejecución para diferentes algoritmos dan lugara diferentes clases de complejidad. Cada clase de complejidad se caracteriza por una familia de curvas distinta. Todas las curvas de una clase de complejidad concreta tienen la misma forma básica, pues solo se diferencian entre ellas por el valor de sus constantes. La notación O (también llamada O mayúscula), se utiliza para comparar la eficiencia de los algoritmos. La notación O se centra en eltérmino dominante an2 (es decir, en aquel que más crece cuando n aumenta; tal y como se observa en la Tabla2), e ignora el resto de términos. Por lo tanto, desprecia también la constante de proporcionalidad a. Así:
O(an2 + bn + c) = O(an2) = O(n2)

f(n)=an2+bn+c
donde a = 0,0001724, b = 0,00400, c = 0,1

n

f(n)

an2

Término n2 como % del total

125 250 500 1000 2000

2.8 11.043.4 172.9 690.5

2.7 10.8 43.1 172.4 689.6

94.7 98.2 99.3 99.7 99.9

Propiedades Notación O
O( f(x) ) + k O( k f(x) ) O( f(x) ) * O( g(x) ) O( f(x) ) + O( g(x) ) g(x) ) ) = = = = O( f(x) ) O( f(x) ) O( f(x) * g(x) ) max ( O( f(x) ), O(

Complejidad de Sentencias en Java
REGLA 1 - CICLOS FOR: El tiempo de ejecución de un ciclo for es, como máximo, el tiempo de ejecución de lasinstrucciones que están en el interior del ciclo (incluyendo las condiciones) por el número de iteraciones. Se supone que las sentencias simples tienen un tiempo de ejecución constante. REGLA 2 - CICLOS FOR ANIDADOS: Analizarlos de adentro hacia afuera. El tiempo de ejecución total de una proposición dentro del grupo de ciclos for anidados es el tiempo de ejecución de la proposición multiplicado por elproducto de los tamaños de todos los ciclos for. REGLA 3 - PROPOSICIONES CONSECUTIVAS: Simplemente se suman REGLA 4 - CONDICION IF THEN /ELSE: if (expresión) instrucción1 else instrucción2 su tiempo de ejecución nunca es más grande que el tiempo de ejecución de la expresión más el mayor de los tiempos de ejecución de la instrucción1 y la instrucción2.

Complejidad de un Algoritmo
A continuación semuestra un ejemplo de cálculo de subsecuencia de suma máxima resuelto de tres formas diferentes y cómo influye su resolución en la complejidad del algoritmo. Dada la secuencia de enteros (posiblemente negativos) A1, A2, ..., An, encontrar (e identificar la subsecuencia correspondiente) el valor máximo de Σ j k=i Ak. Cuando todos los enteros son negativos entenderemos que la subsecuencia de sumamáxima es la vacía, siendo su suma cero.
Por ejemplo para la entrada {-2, 11, -4, 13, -5, 2}, la respuesta es 20. Y para {-2, 11, 1}, la respuesta es 12. Se marca en negrita la subsecuencia de suma máxima

Subsecuencia de suma máxima I
public static int subsecuenciaSumaMaxima (int { int sumaMax = 0; for (int i = 0; i < a.length; i++) for (int j = i; j < a.length; j++) { int sumaActual = 0;...