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

Imágen de pdf Tema 5: Complejidad algorítmica

Tema 5: Complejidad algorítmicagráfica de visualizaciones

Publicado el 5 de Julio del 2020
112 visualizaciones desde el 5 de Julio del 2020
190,2 KB
76 paginas
Creado hace 13a (24/04/2007)
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
  • Links de descarga
http://lwp-l.com/pdf17872

Comentarios de: Tema 5: Complejidad algorítmica (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad