tema2. algoritmia elemental. resumen

5/28/2018 Tema2. Algoritmia Elemental. Resumen

1/13

Algoritmia elemental.

Octubre 2011

1


2/13

Contenido

ndice

1. Introduccin. 1

2. Eficiencia de algoritmos. 2

2.1. Tiempo de ejecucin. . . . . . . . . . . . . . . . . . . . . . . . 3

3. El caso medio y el caso peor. 4

4. Operacin elemental. 4

5. Necesidad de eficiencia. 6

6. Bsquedas lineal y binaria. 6

7. Ordenacin. 9

7.1. Insercin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97.2. Seleccin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1. Introduccin.

En el captulo anterior hemos visto varios algoritmos que nos permitanmultiplicar dos nmeros naturales. Cada pareja a los que se les aplicaba elalgoritmo era un ejemplar o caso del problema.

Un problema ms general es multiplicar dos nmeros naturales quetiene un conjunto infinito de ejemplares.

Un algoritmo debe funcionar correctamente en todos los ejemplares delproblema que manifiesta resolver. Recordar que un algoritmo debe especificarsu dominio de definicin o conjunto de valores que admite como sus entradas.

Espacio de almacenamiento.Puesto que debe ejecutarse por una m-quina real en su ejecucin pueden presentarse problema de almacenamientode variables, memoria del ordenador, etc. Para obviar estos problemas su-

pondremos que el ejecutor es una mquina ideal, sin limitacin fsica alguna.

Eleccin de un algoritmo. Para resolver un problema podemos tenera nuestra disposicin varios algoritmos. Para seleccionar el mejor, podemos


3/13

seguir varios criterios. Como criterios o ideas generales tenemos:

Enfoque emprico (o a posteriori): una vez probados sobre varios ejem-plares, se toma el de mejor rendimiento.

Enfoque terico (o a priori).Se analizan los recursos necesarios paracada algoritmo como funcin del tamao de los casos considerados. Losrecursos que ms interesan son el tiempo de computaciny el espaciode almacenamiento.

2. Eficiencia de algoritmos.

De las condiciones exigidas a un algoritmo (vase Tema 1), la ms intere-

sante es la efectividad(ha de ser ejecutable en tiempo finito), lo que dependede los recursos y de ellos el ms importante es el tiempo de ejecucin ydespus el espacio de almacenamiento.

Entenderemos por eficiencia la rapidez con que se ejecuta que suele estaren relacin directa con el tamao del ejemplar considerado.

Tamao de un ejemplar

Cualquier entero positivo que mida de algn modo el nmero de suscomponentes. Por ejemplo:

Problema Tamao

Bsqueda en una lista Nmero de elementos de la listaMultiplicar dos matrices Dimensiones de las matrices

Ordenar una lista Nmero de elementos de la lista

Recorrer un rbol binario Nmero de nodos del rbol

Resolver SEL Nmero de ecuaciones y/o incgnitas

Explorar y recorrer grafos Nmero de nodos y/o aristas

Este planteamiento para el tamao de un problema es terico y no de-pende de la mquina, ni del lenguaje de programacin, ni de las habilidadesdel programador.

Principio de Invarianza

A la hora de usar distintos compiladores o lenguajes de programacin,claramente un algoritmo no tardar lo mismo en ejecutarse. Por ello nopodramos hablar de un algoritmo con un tiempo de ejecucin exactamenteT(n).

2


4/13

Se puede dar una idea aproximada del tiempo de ejecucin mediante el

principio de invarianza, por el que dos implementaciones del algoritmo enuna mquina real no difieren en su eficiencia en ms de un factor constante.

Es decir, ante un ejemplar de un problema de tamao n un algoritmotardaT1(n)yT2(n)en dos mquinas distintas, entonces existenC1, C2 R

0

tales que paran es

T1(n) C2T2(n), T2(n) C1T1(n)

2.1. Tiempo de ejecucin.

Tiempo de ejecucin de orden

Definicin: 1. Decimos que un algoritmo requiere un tiempo de ejecucinde ordenT(n) si existe una implementacin del algoritmo capaz de resolvercualquier ejemplar de tamaonen un tiempo inferior aC T(n) siendo C unnmero real positivo. Lo denotaremosO(T(n)).

La constante C depender de la mquina y/o del lenguaje. Segn laforma de T(n) se dir que el algoritmo es lineal, cuadrtico, polinomial,exponencial, etc.

Usualmente no se conocen las constantes ocultas que afectan aT(n)o nointeresan, pero no se pueden olvidar por completo dichas constantes ocultas.

Ejemplos

Cuidado: Considerar dos algoritmos cuyas implementaciones en ciertamquina requieren n2 das y n3 segundos, respectivamente. Solamente enalgoritmos que requiera 20 millones de aos para resolverlos, el algoritmocuadrtico ser mejor que el cbico. Sin embargo, desde el punto de vistaterico el primero es asintticamentemejor.

Al implementar un algoritmo se obtiene que su tiempo de ejecucin esT(0) = 1, T(1) = 4, T(n) = (n+ 1)2 para n 2. Probar que el tiempo deejecucinest en el ordenden2.

Solucin: Necesitamos una constante C y un nmero natural n0 queverifique (n+ 1)2 C n2.

Podemos tomar, por ejemplo, n0= 1 y C= 4, n0= 3 y C= 2, etc.

Demostrar que T(n) = 4n3 + 2nes O(n3).Al igual que utilizamos la notacin O para dar una cota superior del

tiempo de ejecucin, la notacin que utilizamos para dar una cota inferiordel mismo, es:

3


5/13

Diremos que el tiempo de ejecucin T(n) de un algoritmo es (f(n)) si

existec R0 y n0 Ntal que T(n) cf(n)para todon n0

Diremos que el tiempo de ejecucin de un algoritmo es de (f(n)), si esa la vez O(f(n)) y (f(n))

Demostrar que T(n) = 3n3 + 2n2 es de (n3)

3. El caso medio y el caso peor.

El tiempo de ejecucin, muchas veces, no depende slo del tamao de laentrada, si no de la entrada particular. Esta dependencia se puede estudiarmediante dos mtodos:

Anlisis de caso medio: se analiza el tiempo de ejecucin para todas lasentradas de tamaon y se hace su media. Y s no todas las entradasson equiprobables?

Anlisis del caso peor: localiza la entrada que haga ms largo el tiempode ejecucin del algoritmo; es decir la que realice todos su pasos o lagran mayora si hay sentencias condicionales. Es el que utilizaremospor defecto

4. Operacin elemental

Es aquella cuyo tiempo de ejecucin se puede acotar superiormente poruna constante, que no depende del tamao del ejemplar ni de los parme-tros que se est considerando, puede depender de la implementacin, de lamquina, del programa usado.

Operacin elemental: El el siguiente algoritmo Suma, que calcula lasuma de los n primeros nmeros naturales, se puede considerar elemental lainstruccins = s + i, siempre y cuando consideremos los nmeros involucra-dos pequeos, si son grandes no.

intSuma (intn)ENTRADA: nenteroSALIDA: La suma1 + 2 + +n

1. s= 0

2. para i = 1 hasta n hacer

3. s= s+i

4


6/13

4. fin para

5. devolver (s)

Operacin no elemental: El el siguiente algoritmo SumaRecu, quecalcula la suma de los n primeros nmeros naturales, evidentemente no eselemental la instruccin si entonces sino

intSumaRecu (intn)ENTRADA: nenteroSALIDA: La suma1 + 2 + +n

1. Sin= 1 entonces

2. devolver(n)3. si no

4. devolver(n)+SumaRecu(n 1)

5. fin si

Ejemplo

Sea a[1 n] un array de n nmeros enteros. Se puede afirmar quex =mn{a[i]; i = 1, 2, , n} es una operacin elemental? Solucin: No,ya que el tiempo de ejecucin crece con n. Esa instruccin es una abreviatu-ra dex=Minimo(a) con la funcin Minimo dada por

array Minimo (array a)ENTRADA: a[1 n] array den enterosSALIDA: mn{a[i]; i= 1, 2, , n}

1. x= a[1]


3. sia[i]< x entonces

4. x= a[i]

5. fin si

6. fin para

7. devolver(x)

con al menos n operaciones elementales si entonces

5


7/13

5. Necesidad de eficiencia

Es necesaria la eficiencia?

Esencialmente es la velocidad de crecimiento de un algoritmo la que de-termina el tamao de un problema que se puede resolver en una mquina.

A menos que un algoritmo tenga una velocidad de crecimiento tan bajacomoO(ln(n)) u O(n) un incremento pequeo en la rapidez de la mquinano influye en el tamao del problema ms grande que se pueda resolver.

Por tanto, es necesaria la eficiencia de un algoritmo y no la fuerza bruta.Veamos algn ejemplo.

Ejemplo

SeanA1, A2 yA3 tres algoritmos para resolver un problema. Se sabe queen una determinada mquina el tiempo de ejecucin no supera 100n,5n2 y3n, respectivamente. Cul es ms eficaz?

Una tabla con los primeros valores de las acotaciones par los tres algo-ritmos es;

Ejemplo

n A1 A2 A3

1 100 5 3

2 200 20 6

3 300 45 27

4 400 80 815 500 125 243

6 600 180 729...

... ...

...

19 1900 1805

20 2000 2000

21 2100 2205 ...

... ...

...

6. Algoritmos de Bsqueda

LinearSearch

En el contexto de bsqueda y ordenacin, supondremos que los elementoslo son de un conjunto ordenado.

6


8/13

Seaa[1 n] una secuencia de n elementos. El problema consiste en de-

terminar si un elemento x es de a.Six a hallar un ndice j ; 1 j n tal que x= a[j]; si no j = 0.Se llama bsqueda secuencial o lineal, ya que el mximo nmero de com-

paraciones crece linealmente con n.Tambin estudiaremos el algoritmo de bsqueda binaria.array LinearSearch (array a, intx)ENTRADA: a[1 n] array den elementos x ZSALIDA: Six a el ndice de x ena, sino, el nmero 0.

1. i= 2

2. mientras (i n) (a[i]=x) hacer

3. i= i+ 1

4. fin mientras

5. sii > n entonces

6. i= 0

7. fin si

8. devolver(i)

Notar que tal como est escrito devuelve el primer ndice j encontrado.

En el peor caso debe compara x con todas las entradas de a, su orden esO(n).En promedio1 el tiempo de ejecucin del algoritmo LinearSearches:

1. Six a es A(n) =n

i=1

i

n=

n+ 1

2

2. Six a x /a es A(n) =n

i=1

q

ni+ (1 q)n= q

n+ 1

2 + (1 q)n

dondep es la probabilidad de que x a. En ambos casos A(n) (n).Sip = 1, esA(n) = n+12 , y se examinan en promedio 50 %y sip = 1/2

esA(n) = 3n+1

4 y ahora75 %.array BinarySearch (array a, int x)ENTRADA: a[1 n] array con a[1] a[2] a[n]x ZSALIDA: Six a el ndice de x ena, sino, el nmero 0.

1Por comodidad de razonamiento supondremos que todos los elementos son distintos

7


9/13

1. l= 1; h= n; j = 0

2. mientras (l h) (j = 0) hacer

3. m= (l+h)/2

4. six = a[j] entonces

5. j=m

6. si no

7. six < a[m] entonces

8. h= m 1

9. si no

10. l= m+ 1

11. fin si

12. fin si

13. fin mientras

14. devolver(j)

Ejemplo: 1. Considerar el array

a[1 14] = (1, 4, 5, 7, 8, 9, 10, 12, 15, 22, 23, 27, 32, 35)

Como instancia buscamosx= 22. Comparamos cona(1 + 14)/2= a[7] =10. Como 22> a[7] y el array est ordenado, x no puede estar ena[1 7]Ahora comparamos cona(8+14)/2= a[11]. Como22 < a[11] descartamosla porcin a[11 14] del array y la bsqueda queda reducida a a[8 10].Comparamos x con a(8 + 10)/2 = a[9]. Como 22 > a[9] descartamosa[8 9] y la nica entrada que puede ser alcanzada esa[10] = 22.

Teorema: 1. El nmero de comparaciones realizadas por el algoritmo Bi-

narySearch en un array ordenado de tamao n es a lo mslog n + 1.

Notar que el mnimo nmero de comparaciones es 1. Para calcular el n-mero mximo, supongamos que x a[i]; 1 i n. El nmero de elementosrestantes en la segunda iteracin es n/2, ya que si n es impar es n/2 y sies par es (n 1)/2.

8


10/13

Anlogamente, en la tercera iteracin es n/2/2= n/4.

En el jsimo paso, el nmero de elementos restante es n/2j

1. Laiteracin contina hasta que el tamao de la subsecuencia es 1 encontremosax. Por tanto, el mximo nmero de iteraciones para encontrar x es el valordej tal que n/2j1= 1.

Es decir,1 n/2j1


11/13

SALIDA: Array a[1 n] ordenado en orden creciente


2. x= a[i], j=i 1

3. mientras (j >0) (a[j]> x) hacer

4. a[j+ 1] = a[j]

5. j=j 1

6. fin mientras

7. a[j+ 1] =x

8. fin para

9. devolver(a[1 n])

Ejemplo Dados el array a = (5, 2, 4, 6, 1, 3) observar el comportamientodel algoritmo InsertionSort

Dado el arraya[30, 12, 13, 13, 44, 12, 24, 13]aplicar el algoritmo Insertion-Sort, contabilizando el nmero de operaciones que se efectan. Lo mismo siel array es a = (4, 3, 12, 5, 6, 7, 2, 9)

Proposicion: 1. El nmero de comparaciones efectuadas por el algoritmo

InsertionSort est entre n 1 y n(n+1)2 . El nmero de asignaciones esigual al nmero de comparaciones ms n 1. Decimos que la complejidaddel algoritmo es de ordenn2.

Anlisis del caso peor: Para cada i [2 n] el mximo nmero decomparaciones posibles en el bucle mientrasdel algoritmo es i 1 (cuandoel array est en orden descendente), luego en total se efectan W(n) =n

i=2

(i 1) =n(n 1)

2 Por tantoW(n) O(n2)

Anlisis del caso medio:Supondremos los elementos distintos y todaslas permutaciones equiprobables. Calcularemos cuntas comparaciones se ha-

cen en promedio para insertara[i]en orden con los anterioresa[1], , a[i1],es decir cuantas iteraciones del bucle mientras se hacen en promedio paracada valor del item i

Anlisis del caso medio: Cuntas iteraciones del bucle mientas sehacen en promedio para cada valor del item i?

10


12/13

Hay i posiciones a las que x = a[i] puede ir. Para ubicar al item x en:

a[1] se necesitan i 1comparaciones.a[2] se necesitani 1comparaciones.a[3]se necesitani 2comparaciones.

...a[i 1]se necesitan2 comparaciones.a[i] se necesitan 1comparacin.

Adems la probabilidad de que x se ubique en cualquiera de las i posi-ciones es la misma.

Anlisis del caso medio: El promedio de comparaciones para insertarx= a[i] en a[1], , a[i 1] ser

i 1

i +

(i 1) + (i 2) + + 2 + 1

i =

i2 +i 2

2i =

i+ 1

2

1

i

Sumando todas las posiciones i [2 n]es

A(n) =n

i=2

i+ 1

2

1

i

=

3 + 4 + + (n+ 1)

2

ni=2

1

i

(n+ 4)(n 1)

2 ln(n). Evidentemente A(n) O(n2).

Notar que la ordenacin es in situ y que el algoritmo es sensible a laordenacin previa de a

7.2. Ordenacin iterativa por seleccin.

El algoritmo iterativo de ordenacin por seleccin SelectionSorttrabajade forma muy simple: primero selecciona el menor elemento de a y lo colocaena[1], luego selecciona el mnimo de los restantesn1elementos y lo colocaena[2].

Contina hasta que en la ltima iteracin, al penltimo elemento msgrande lo coloca en a[n 1], quedando as el mayor en a[n].

array SelectionSort (array a)ENTRADA: aarray de tamao n, con n 1SALIDA: El arraya ordenado segn

1. para i = 1 hasta n 1 hacer

2. /*Se supone, de momento, que el mnimo est en a[i]*/

3. m= i

4. /*Ahora se localiza la posicin del mnimo*/

11


13/13

5. para j=i+ 1 hasta n hacer

6. sia[j]< a[m]

7. m= j

8. fin si

9. fin para

10. /*Se intercambian el mminoa[m] con a[i]*/

11. x= a[m]; a[m] =a[i]; a[i] =x

12. fin para

13. devolver(a)

Se toma n como tamao de la entrada y como medida del tiempo eltiempo de ejecucin de la instruccin barmetro si entonces

Proposicion: 2. W(n) O(n2)

El nmero de veces que se ejecuta dentro de los bucles la instruccinbarmetro (6) Si a[j]< a[m] entonces... es

n1

i=1

n

j=i+1

1 =n(n 1)

2

No es relevante que a est ordenado.

Proposicion: 3. Sean el tamao del arraya[1 n]. Se tienen:

1. El nmero de comparaciones efectuadas por SelectionSort esn(n 1)/2

2. El nmero de elementos intercambiados est entre0 yn 1

3. El nmero de asignaciones efectuadas est entre0 y3(n 1), ya quecada intercabio requiere tres asignaciones.

Ejercicio:Escribir un algoritmo recursivo de ordenacin por seleccin quellamamos SelectionSortRecu. Empezamos con SelectionSortRecu(a,1)?

12

tema2. algoritmia elemental. resumen

Documents