Diapositiva de ejercicio de algoritmo

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 simplerecogida de los tiempos
de ejecución de los algoritmos indudablemente no.
Tamaño del
array n

Ordenador A
(ms)

Ordenador B
(ms)

125

12.5

2.8

250

49.3

11.0

500

195.8

43.4

1000

780.3

172.9

2000

3114.9

690.5

Complejidad
Tiempo de Ejecución

3500
3000
2500
2000

f 1(n)

1500

f 2(n)

1000
500
0
125

250

500

1000

2000T am añ o

f1(n) = 0,0007772n2+0,00305n+0,001

f2(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á lamisma.

Notación O.
Los tiempos de ejecución para
diferentes algoritmos dan lugar a
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 Omayúscula), se utiliza para
comparar la eficiencia de los
algoritmos.
La notación O se centra en el
té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

125

2.8

2.7

94.7

250

11.0

10.8

98.2

500

43.4

43.1

99.3

1000

172.9

172.4

99.7

2000

690.5

689.6

99.9

Término n2
como %
del total

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 las
instrucciones 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 deadentro 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 el producto 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 esmá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 se muestra 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 suma má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...