Técnicas de Programación Avanzadas (TPA) 1...20/1/17 1 Técnicas de Programación Avanzadas (TPA)...

20/1/17

1

TécnicasdeProgramaciónAvanzadas(TPA)

Tema1.Eficienciadelosalgoritmos

Tema1.Eficienciadelosalgoritmos

1. Criteriosparamedirlaeficienciadeunalgoritmo2. Tiempodeejecución3. Ordendemagnitud4. Reglasparacalcularlacomplejidaddelcódigo5. Complejidadencódigorecursivo

20/1/17

2

Criteriosparamedirlaeficienciadeunalgoritmo

§ Paraunmismoproblemasepuedendiseñardistintosalgoritmos(soluciones)queloresuelvancorrectamente.

§ Debepodersedeterminarquéalgoritmoutilizar.

§ Ejemplo:¿Cuáleslamejorruta?– Lamáscorta.

– Lamásrápida.

– Laquenotengapeajes.

TécnicasdeProgramaciónAvanzadas(TPA)

Criteriosparamedirlaeficienciadeunalgoritmo

§ Paraellosecompararánsegúnuncriteriodeterminado.Losmásusuales:– Legibilidadyfacilidaddecomprensión,codificaciónydepuración.– Usoeficientedelosrecursos:tiempodeejecuciónyespaciode

memoria.– (Otros:reutilización,documentación,portabilidad,etc.)

§ Mediremoslaeficiencia segúnelsegundodeloscriterios(losprimerossepresuponen).

TécnicasdeProgramaciónAvanzadas(TPA)

20/1/17

3

Criteriosparamedirlaeficienciadeunalgoritmo

§ Lamemoria yanoesunrecursocríticoàmediremoslaeficienciadeunalgoritmobasándonoscasisiempreensutiempodeejecución.

§ Eltiempodeejecuciónnodependerádelapotencia delamáquinadondeseejecuta.Habráqueestudiarloenfuncióndelalgoritmo utilizado.

TécnicasdeProgramaciónAvanzadas(TPA)

Tema1.Eficienciadelosalgoritmos

1. Criteriosparamedirlaeficienciadeunalgoritmo2. Tiempodeejecución3. Ordendemagnitud4. Reglasparacalcularlacomplejidaddelcódigo5. Complejidadencódigorecursivo

20/1/17

4

Tiempodeejecución

§ Engeneral,eltiempodeejecucióndeunprogramadependedevariosfactores:

1. Nºdevecesqueseejecutacadainstrucción.2. Compiladorutilizado(unainstruccióndealtonivelse

puedetraduciralenguajemáquinadediferentesformas).

3. Elordenadorutilizado(puedevariareltiempodeejecucióndecadainstrucciónmáquina).

§ Nosbasaremossóloenelprimerfactor.Losdemásnosepuedenpresuponer.

TécnicasdeProgramaciónAvanzadas(TPA)

Tiempodeejecución

§ Realizaremosunaestimación aprioridelafrecuenciadeejecución.

§ Eneltiempodeejecucióndeuncasoconcretotambiéninfluye:

– Nºdedatosdeentrada,– Estructuradelaentrada,– Distribucióndelaentrada.– Calidaddelcódigofuenteycalidaddelcódigo

máquinaè nosecalculaelnºdeinstruccionesejecutadas,sinoelnºdevecesqueseejecutacadainstrucción.

TécnicasdeProgramaciónAvanzadas(TPA)

20/1/17

5

Tiempodeejecución

§ Dependiendodelaentradadelproblema,puedendarse3casos:

• CasoPeor:eltiempodeejecuciónesmáximo.• CasoMejor:eltiempodeejecuciónesmínimo.• CasoMedio:casomásprobable.Tiempodeejecución

=mediaestadísticadetodosloscasosposibles.

§ Paraprobarlaeficienciadeunalgoritmousaremoscomomedidaeltiempodeejecuciónenelpeorcaso:T(n).

TécnicasdeProgramaciónAvanzadas(TPA)

Tiempodeejecución

§ Ejemplo:– ¿CuántasvecesseejecutacadainstrucciónsieltamañoN

delalistaes4?¿Ysies6?

boolean buscar (TElemento item, Lista L) {{Pre: N>0}{Post: Buscar = $i:1<=i<=N: L[i]=item}boolean encontrado = false;int cont = 0;while ((!encontrado) && (cont < L.longitud())){

cont++; encontrado = L[cont] == item;

}return encontrado;

}

TécnicasdeProgramaciónAvanzadas(TPA)

12

34

5

6

20/1/17

6

Tiempodeejecución

§ Enelpeordeloscasos:

– Amedidaqueseincrementaeltamañon delalista,elvalordeT(n) crecedemaneraproporcionalanè T(n)tieneunordendemagnitudden.

TécnicasdeProgramaciónAvanzadas(TPA)

Instrucción Código Ejecuciones

1 boolean encontrado = false; 1

2 int cont = 0; 1

3 while ((!encontrado) &&

(cont < L.longitud()))n+1

4 cont++; n

5 encontrado = L[cont] == item; n

6 return encontrado; 1

Total 3n+4

Tiempodeejecución

§ T(n)Î O(f(n)),si$ ctes cyn0 talqueT(n)£ c*f(n)," n³ n0§ T(n)ÎW(g(n)),si$ ctes cyn0 talqueT(n)³ c*g(n), " n³ n0§ T(n)ÎQ(h(n)),siysóloT(n)Î O(h(n))yT(n)ÎW(h(n))

§ SiT(n)ÎO(f(n))à T(n)nuncacrecemásrápidoquef(n).

§ SiT(n)ÎW(g(n))à T(n)crece,almenos,almismoritmoqueg(n)

§ SiT(n)ÎQ(h(n))à representaexactamentelatasadecrecimientodeT(n)

TécnicasdeProgramaciónAvanzadas(TPA)

20/1/17

7

Tema1.Eficienciadelosalgoritmos

1. Criteriosparamedirlaeficienciadeunalgoritmo2. Tiempodeejecución3. Ordendemagnitud4. Reglasparacalcularlacomplejidaddelcódigo5. Complejidadencódigorecursivo

Tiempodeejecución

§ Reglasparaelcálculodecomplejidaddeunalgoritmo

1. SiT1(n)Î O(f(n))yT2(n)Î O(g(n)),entonces:

a) T1(n)+T2(n)ÎMax(O(f(n)),O(g(n)))b) T1(n)*T2(n)Î O(f(n)*g(n))

2. SiT(x)esunpolinomiodegradogà T(x)Î O(xg)

TécnicasdeProgramaciónAvanzadas(TPA)

20/1/17

8

Tiempodeejecución

§ Definiremosunarelaciónentrelosdistintosórdenesdemagnituddelasfuncionesf(n)(siempreválidaapartirdeunn0determinado):O(1)<O(logn)<O(n)<O(n·log n)<O(n2)<O(n3)<...<O(2n)<O(n!)<O(nn)

" n>=n0§ Estanotación(O)indicaunlímitesuperior def(n).

Ejemplo:sif(n)esO(n2)à tambiénesO(n3),O(2n)...

§ Alhallarlacomplejidadsedesprecianlasctes deproporcionalidad.– Inconveniente:nomuybuenoparavalorespequeñosdela

entrada.Ejemplo:

T1(n)=5n3 =O(n3)T2(n)=100n2=O(n2)5n3/100n2=n/20à paran<20,T1 esmejor.

TécnicasdeProgramaciónAvanzadas(TPA)

Tiempodeejecución

TécnicasdeProgramaciónAvanzadas(TPA)

0

5

10

15

20

25

30

35

40

45

50

0 1 2 3 4 5 6 7 8 9 10

n

log2n

n·log2n

sqr(n)

n2

n3

2n

0

200

400

600

800

1000

1200

0 2 4 6 8 10 12 14 16 18 20

n

log2n

n·log2n

sqr(n)

n2

n3

2n

20/1/17

9

Tiempodeejecución

TécnicasdeProgramaciónAvanzadas(TPA)

0

5

10

15

20

25

30

35

40

45

50

0 1 2 3 4 5 6 7 8 9 10

n

log2n

n·log2n

sqr(n)

n2

n3

2n

0

200

400

600

800

1000

1200

0 2 4 6 8 10 12 14 16 18 20

n

log2n

n·log2n

sqr(n)

n2

n3

2n

Tema1.Eficienciadelosalgoritmos

1. Criteriosparamedirlaeficienciadeunalgoritmo2. Tiempodeejecución3. Ordendemagnitud4. Reglasparacalcularlacomplejidaddelcódigo5. Complejidadencódigorecursivo

20/1/17

10

Reglasparacalcularlacomplejidaddelcódigo

§ ¿Cómosetraducetodoestoalahoradecalcularlacomplejidaddenuestrocódigo?– Aplicaremosdiferentesherramientas– Dependerándeloselementosoestrategiasdeprogramaciónutilizadas

§ Sentenciassimples– CadainstrucciónmáquinaseejecutaenuntiempoconstanteKi.– EscogemoscomounidadelmayortiempoKi.– CadasentenciaseconsideradeO(1).– Válidoparamanipulaciones(asignaciones,comparaciones,etc.)sobredatos

simples.§ Composiciónsecuencial:

– Paraunasecuenciadesentenciasà elmáximodetodasellas.

TécnicasdeProgramaciónAvanzadas(TPA)

Reglasparacalcularlacomplejidaddelcódigo

§ SelecciónCondicional(If then else,Case):– Deentretodoslosposiblescaminosà elmáximoencomplejidad.

§ Repeticiones:– å (complej.cuerpobucle+complej.condiciónterminación)

§ Llamadasaotrosmódulos(procedimientosofunciones):– Comosifuesenotraspartesdelprograma

TécnicasdeProgramaciónAvanzadas(TPA)

20/1/17

11

Reglasparacalcularlacomplejidaddelcódigo

§ Ejemplos:

– x=x+1 O(1)

– for (i=1;i<=N;i++){X=X+1; O(n)

}

– for (i=1;i<=N;i++){for (j=1;j<=N;j++){x=x+1; O(n2)}

}

TécnicasdeProgramaciónAvanzadas(TPA)

Reglasparacalcularlacomplejidaddelcódigo

§Ejemplo:

voidburbuja(TElementoA[]){for (inti=1;i<=A.length;i++){

for (j=A.length;j>i;j--){if (A[j-1]>A[j]){

TElementotemp=A[j-1];A[j-1]=A[j];A[j]=temp;

}}

}}

TécnicasdeProgramaciónAvanzadas(TPA)

20/1/17

12

Reglasparacalcularlacomplejidaddelcódigo

§Fórmulashabituales:

TécnicasdeProgramaciónAvanzadas(TPA)

å

å

å

=

=

=

++=

+=

=

n

i

n

i

n

i

nnni

nni

n

1

2

1

1

6)12)(1(

2)1(

1 åå==

- ==n

i

n

in

ii

11

1 )log(1

T(n)=

T(n)ÎQ(nk+1)sia=1T(n)ÎQ(andivb)sia>1

Reglasparacalcularlacomplejidaddelcódigo

§ Recursividad1. ReducciónporSUSTRACCIÓN2. ReducciónporDIVISIÓN

§ Reducciónporsustracción

TécnicasdeProgramaciónAvanzadas(TPA)

c0nk0 si 0 <= n < b

a·T(n - b) + c1nk si n >=b

Complejidaddelcasobase

Complejidaddelcasogeneral Parte

recursivaParteNOrecursiva

a: número de llamadas recursivas idénticas en cada invocación del programa

n-b: tamaño de los subproblemas generados

nk:: coste de las instrucciones que no son llamadas recursivas

20/1/17

13

T(n)=

T(n)Î Q(nk)sia<bk

T(n)Î Q(nklogb n)sia=bk

T(n)Î Q(nlogba)sia>bk

Reglasparacalcularlacomplejidaddelcódigo

§ Recursividad1. ReducciónporSUSTRACCIÓN2. ReducciónporDIVISIÓN

§ Reducciónpordivisión

TécnicasdeProgramaciónAvanzadas(TPA)

c0nk0 si 0 <= n < b

a·T(n / b) + c1nk si n >=b

a: número de llamadas recursivas idénticas en cada invocación del programa

n-b: tamaño de los subproblemas generados

nk:: coste de las instrucciones que no son llamadas recursivas