PDF de programación - Tema 5: Complejidad algorítmica

Departamento de Informática
Universidad de Valladolid
Campus de Segovia
______________________

TEMA 5:

COMPLEJIDAD
ALGORÍTMICA

COMPLEJIDAD ALGORÍTMICA

• Conceptos básicos.
• Medidas de comportamiento asintótico.
• Reglas prácticas para hallar el coste
• Útiles matemáticos
• Complejidad de algoritmos de búsqueda y ordenación

DEFINICIÓN DE ALGORITMO

• Un algoritmo implica la descripción precisa de los

pasos a seguir para alcanzar la solución de un
problema dado.

• Por pasos se entiende el conjunto de acciones u

operaciones que se efectúan sobre ciertos objetos.

Algoritmo: Entrada

Salida

Proceso

CARACTERÍSTICAS DE UN

ALGORITMO

• Un algoritmo debe poseer las siguientes

características:

– Precisión: Un algoritmo debe expresarse sin ambigüedad.

– Determinismo: Todo algoritmo debe responder del mismo

modo antes las mismas condiciones.

– Finito: La descripción de un algoritmo debe ser finita.

CUALIDADES DE UN ALGORITMO

• Un algoritmo debe ser además:

– General: Es deseable que un algoritmo sea capaz de
resolver una clase de problemas lo más amplia posible.

– Eficiente: Un algoritmo es eficiente cuantos menos recursos

en tiempo, espacio (de memoria) y procesadores consume.

• Por lo general es difícil encontrar un algoritmo que

reúna ambas por lo que se debe alcanzar un
compromiso que satisfaga lo mejor posible los
requisitos del problema.

COMPLEJIDAD ALGORITMICA.

• La complejidad algorítmica representa la
cantidad de recursos (temporales) que
necesita un algoritmo para resolver un
problema y por tanto permite determinar la
eficiencia de dicho algoritmo.

• Los criterios que se van a emplear para

evaluar la complejidad algorítmica no
proporcionan medidas absolutas sino
medidas relativas al tamaño del problema.

EL TIEMPO EMPLEADO POR EL
ALGORITMO SE MIDE EN PASOS

• La medida del tiempo tiene que ser independiente:

– de la máquina
– del lenguaje de programación
– del compilador
– de cualquier otro elemento hardware o software que influya en

el análisis.

• Para conseguir esta independencia una posible
medida abstracta puede consistir en determinar
cuantos pasos se efectúan al ejecutarse el algoritmo.

COMPLEJIDAD ALGORITMICA.

CONCEPTOS BÁSICOS

• El tiempo empleado por el algoritmo se mide en

pasos.

• El coste depende del tamaño de los datos.
• A la hora de evaluar el coste se debe de tener en

consideración tres posibles casos:
– El coste esperado o promedio
– El coste mejor
– El coste peor

• Si el tamaño de los datos es grande lo que importa es

el comportamiento asintótico de la eficiencia.

EL COSTE EN TIEMPO DEPENDE DEL

TAMAÑO DE LOS DATOS

• El tiempo requerido por una algoritmo es función del

tamaño de los datos.

• Por esta razón la complejidad temporal se expresa de

la siguiente forma:

T(n)

• Dependiendo del problema, el tamaño del dato

representa cosas diferentes:
– el número en sí
– el número de dígitos o elementos que lo compone.

• Otra característica importante es que no todos los

datos, dentro de un problema, poseen la misma
importancia de cara a la complejidad algorítmica.

EL COSTE EN TIEMPO DEPENDE DEL

TAMAÑO DE LOS DATOS

• Ejemplo 1: Algoritmo que determina la paridad de un

número restando 2 sucesivamente mientras el
resultado sea mayor que 1 para finalmente comprobar
el resultado.
– El problema tendrá n DIV 2 restas (depende de n).

• Ejemplo 2: Algoritmo de suma lenta

while b>0 do begin

a:=a+1;
b:=b-1;

end;
– En este caso T=T(b).

EL COSTE ESPERADO, EL MEJOR Y EL

PEOR

• Otra característica es que la complejidad algorítmica no

sólo depende del tamaño sino del propio dato en sí.

EL COSTE ESPERADO, EL MEJOR Y EL

PEOR

type
tintervalo=0..N;
tvector=array[1..N] of integer
FUNCTION Busquedasecord(v:tvector;elem:telem):tintervalo
var

i:tintervalo;

begin

i:=0;
repeat

i:=i+1;

until (v[i]>=elem) or (i=N);
if v[i]=elem then

Busquedasecord:=i

else

End;

Busquedasecord:=0

En este algoritmo se pueda
dar las siguientes situaciones:
- Caso mejor: el elemento este
en la primera posición.
- Caso peor: Se tenga que
recorrer todo el vector.
- Caso promedio o esperado:
Puesto que todas la posiciones
son equiprobables el tiempo
será n/2 pasos.

EL COSTE ESPERADO, EL MEJOR Y EL

PEOR. NOTACIÓN

• Tmax(n): Representa la complejidad temporal en el peor

de los casos.

• Tmin(n): Representa la complejidad en el mejor de los

casos posibles.

• Tmed(n): Expresa la complejidad temporal en el caso
promedio. Para su cálculo se suponen que todas las
entradas son equiprobables.

EL COSTE ESPERADO, EL MEJOR Y EL

PEOR. EJEMPLO

• Cálculo de Tmax, Tmin, y Tmed para el algoritmo de búsqueda

secuencial ordenada:

• Nomenclatura del tiempo constante empleado por las

siguientes operaciones:
– suma:‘s’
– comparación: ‘c’
– asignación: ‘a’

EL COSTE ESPERADO, EL MEJOR Y EL

PEOR. EJEMPLO

Tmin: Este tiempo se calcula cuando v[1]>=elem.

Tmin=3a+3c+s=constante

Tmax:Este tiempo se calcula cuando v[n]<=elem

Tmax=a +n(s+2c+a)+c+a=n(s+2c+a)+2a+c

Tmax=K1n+K2

EL COSTE ESPERADO, EL MEJOR Y EL

PEOR. EJEMPLO

Tmed:Este tiempo se calcula considerando cualquier entrada

equiprobable. Si T(j)=jK1+K2

Entonces:

T

(

Pj
)

donde

P

=

1

n

T

T

=

)

)

1

(

n

(

n

k
n

1

med

med

n

∑

j

=

=

=

n

∑

j

=
n

∑

j

=

j

+

T

med

(

n

)

=

k

1

1

(

jk

k
n
+

n

j

∑
1
=
(
n
2

1

1

2

1

=
)

+

k

2

)

=

1
n
(
n

1

k
n

+

k

2

=

)
n

1

+
2
nk
1
2

+

k

2

+

1

k
2

+

k

2

=

nc

1

+

c

2

LO IMPORTANTE ES EL COMPORTAMIENTO

ASINTÓTICO

• Tiempos empleados para el cálculo de algoritmos con
distintos ordenes, considerando que el computador en
cuestión ejecuta 1 Millón de operaciones por segundo
(1MHz).

T(n)

n

10
50
100
103
104
105
106

log n
3.3 10-6
5.6 10-6
6.6 10-6

10-5

1.3 10-5
1.6 10-5
2 10-5

n
10-5
5 10-5
10-4
0.001
0.01
0.1
1

n log n
3.3 10-5
2.8 10-4
6.6 10-4

0.01
0.13
1.6
19.9

n2
10-4
0.0025
0.01

1
100
104
106

n3
0.001
0.125

1

2n
0.001

n!
3.63

intratable intratable
intratable intratable
intratable intratable
intratable intratable
intratable intratable intratable
intratable intratable intratable

1000
106

MEDIDAS DEL COMPORTAMIENTO

ASINTÓTICO

EJEMPLO

s
o
s
a
P

s
o
s
a
P

60

50

40

30

20

10

0

300

250

200

150

100

50

0

en

2n2
8n
20lg n

1

2

3

4

5

Tamaño datos

en

2n2

8n

20lg n

1 3 5 7 9

1
1

3
1

5
1

Tamaño dato

7
1

9
1

1
2

3
2

5
2

MEDIDAS DEL COMPORTAMIENTO

ASINTÓTICO

• El orden de la función T(n) expresa el comportamiento

dominante para los datos de gran tamaño.

• Para poder determinar y expresar correctamente el

comportamiento asintótico es conveniente disponer de
una adecuada notación. A continuación se presentan
las notaciones:
– O mayúscula
– Ω Mayúscula
– Θ mayúscula

NOTACIÓN ‘O’ MAYÚSCULA

• Definición: Sean f,g:Z+ R+ , se dice que f∈O(g) o

que f es del orden de g si existen constantes no ∈Z+ y λ
∈R+ tales que:

f(n)≤ λ g(n) para todo n≥no

• Esto significa que f no crece más deprisa que g. De

esta forma acotamos superiormente el comportamiento
asintótico de la función salvo constantes.

• Para el algoritmo de Búsqueda secuencial ordenada:

Tmax(n)=k1n+k2 ∈ O(n) ya que
k1n+k2 ≤ λn para todo n≥k2/(λ-k1)

• Todas las funciones de tiempo constante son O(1).

PROPIEDADES DE LAS NOTACIÓN.

ESCALABILIDAD

• O(logan)=O(logbn)

• Por esta razón no es necesario especificar la base del

logaritmo: O(log n).

PROPIEDADES DE LAS NOTACIÓN. REGLA

DE LA SUMA

• Regla de la suma: Si f1∈O(g1) y f2∈O(g2) entonces f1+f2

∈O(max(g1,g2)).

• La generalización de esta regla junto con la propiedad de

la escalabilidad se expresa de la siguiente forma:

– Si fi ∈O(f) para todo i=1....k entonces:

c1f1+......+ckfk ∈O(f).

– De donde cualquier polinomio pk(n) ∈O(nk)

PROPIEDADES DE LAS NOTACIÓN. REGLA

DEL SUMATORIO

• Regla del sumatorio: Si f∈O(g) y la función g es creciente

entonces:

– Si f(i)=i.

n

∑

i

=

n

∑

i

=

f

(

i

)

∈

O

n

⎛
⎜⎜
⎝

+

∫

1

1

g

(

x

)

dx

i

=

(
n

1

)
n

+
2

=

2

n
2

+

1

1

⎞
⎟⎟
⎠

n
2

n

+

1

n

+

1

2

x

∫

1

dx

1
2
– De donde cualquier polinomio pk(n) ∈O(nk)

+
2

x
2

)1

−

=

=

n

(

1

2

=

2

n
2

+

n

CONSECUENCIA ÚTIL DE LA REGLA DEL

SUMATORIO

n

∑

i

=

K

i

∈

(
nO

k

+

1

)

1

n

+

∫

1

1

k

x

dx

=

x
k

k

+

+

1
1

n

+

1

1

=

k

+

1

(

n

+
k

)1
1
+

−

1
+

1

k

≈

k

1

(
n

+

1

k

)

+

1

+

k

2

∈

(
nO

k

+

)1

JERARQUÍA DE ÓRDENES DE FRECUENTE

APARICIÓN

• Los comportamientos asintóticos de más frecuente

aparición se pueden ordenar de menor a mayor
crecimiento de la siguiente forma:

1<<log n<<n<<n log n<<n2<<n3<<.....<<2n<<n!

REGLAS PRÁCTICAS PARA HALLAR EL

COSTE DE UN ALGORITMO

• Lo que se presenta a continuación son reglas

generales para el cálculo de la complejidad temporal
en el peor de los casos.

• Estas reglas deberán tener en consideración los

costes de:
– Las instrucciones simples
– La composición de instrucciones
– Las instrucciones de selección
– De los bucles
– Los subprogramas

INSTRUCCIONES SIMPLES

• Se considera que se ejecuta en tiempo constante:

– La evaluación de las expresiones aritméticas siempre que los
datos sean de tamaño constante así como las comparaciones
de datos simples.

– Las operaciones de asignación, lectura y escritura de datos

simples.

– Las operaciones de acceso a una componente de un array, a

un campo de un registro y a la siguiente posición de un
registro de un archivo.

• Todas estas operaciones se consideran de Θ(1).

COMPOSICIÓN DE INSTRUCCIONES

• Si suponemos que las instrucciones I1 e I2 poseen

complejidades temporales, en el peor de los casos de
T1(n) y T2(n) respectivamente entonces el coste de la
composición de ambas instrucciones será:

TI1,I2(n)=T1(n)+T2(n)

• Que aplicando la regla de la suma es el máximo de

ambos.

INSTRUCCIONES DE SELECCIÓN

• Para la instrucción condicional:

– if <condic