Analisis busquedas !

2013

Corporación Universitaria Del Caribe CECAR

Facultad de Ingeniería Ingeniería De Sistemas

Análisis De AlgoritmosDOCENTE

Guillermo HernándezESTUDIANTE

Jose Rios

1

2

Tabla de contenidoBibliografía...................................................................................................................................5

1. Análisis de Algoritmos......................................................................................................5

1.1. Algoritmos De Búsquedas.............................................................................................5

1.1.1. Búsqueda Secuencial................................................................................................5

1.1.1.1. Definición:............................................................................................................5

1.1.1.2. Código:..................................................................................................................5

1.1.1.3. Mejor Caso...........................................................................................................5

1.1.1.3.1. Definición.............................................................................................................5

1.1.1.3.2. Conteo de OE........................................................................................................6

1.1.1.4. Peor Casos............................................................................................................6

1.1.1.4.1. Definición.............................................................................................................6

1.1.1.4.2. Conteo de OE........................................................................................................7

1.1.1.5. Pasos promedio....................................................................................................7

1.1.1.6. Grafica Mejor casos vs Peor caso..........................................................................8

1.1.1.7. Teoría vs Practica del conteo de OE......................................................................8

1.1.2. Búsqueda Binaria......................................................................................................9

1.1.2.1. Definición.............................................................................................................9

1.1.2.2. Código...................................................................................................................9

1.1.2.3. Mejor Caso...........................................................................................................9

1.1.2.3.1. Definición.............................................................................................................9

1.1.2.3.2. Conteo de OE......................................................................................................10

1.1.2.4. Peor Caso............................................................................................................11

1.1.2.4.1. Definición............................................................................................................11

1.1.2.4.2. Información para el peor caso............................................................................11

1.1.2.4.3. Conteo de OE......................................................................................................12

1.1.2.4.4. Teoría vs Practica Del Conteo OE........................................................................12

1.1.2.4.5. Grafica Mejor Vs Peor Caso(Tiempo Ejecucion)..................................................13

1.1.3. Método Transponer................................................................................................13

1.1.3.1. Definición............................................................................................................13

1.1.3.2. Código.................................................................................................................14

3

Primera forma........................................................................................................................14

Segunda forma.......................................................................................................................14

1.1.3.3. Evaluar casos......................................................................................................14

1.1.3.4. Grados de complejidad.......................................................................................15

1.1.3.4.1. Primera forma....................................................................................................15

1.1.3.4.2. Segunda Forma...................................................................................................15

1.1.3.4.3. Teoría vs Practica conteo OE..............................................................................15

1.1.3.4.4. Grafica Primer Método Vs Segundo Método......................................................16

4

Bibliografía

UChile. (s.f.). Recuperado el 20 de Septiembre de 2013, de http://users.dcc.uchile.cl/~rbaeza/inf/algoritmia.pdf

wikibooks. (s.f.). wikibooks. Recuperado el 19 de Septiembre de 3013, de wikibooks: http://es.wikibooks.org/wiki/%C3%81lgebra_Lineal/Transpuesta_de_una_matriz

5

1. Análisis de Algoritmos

1.1. Algoritmos De Búsquedas

1.1.1. Búsqueda Secuencial

1.1.1.1. Definición:El método de búsqueda secuencial es la técnica más sencilla de buscar un elemento en un vector, funciona de la siguiente manera; recorrer el vector posición por posición e ir comparando con el valor de cada una de ellas hasta, que encuentre el elemento buscado o hasta que vector sea recorrido totalmente.

1.1.1.2. Código:

1.1.1.3. Mejor Caso

1.1.1.3.1. DefiniciónPara el método de búsqueda secuencial el mejor caso se presenta cuando el elementos a buscar se encuentre alojado en la posición [0] del vector; es decir que el datos este en la primera casilla de arreglo esto que conlleva que el ciclo repetitivo solo hará una sola iteración ya que la instrucción if evalúa que el después que se halle el dato en el índice [0] el if hace un return que evita que el ciclo for haga más de una iteración.

Ejemplo: queremos buscar a 1:

Datos 1 2 4 5 6 7 8 9 9 10Índice

0 1 2 3 4 5 6 7 8 9

6

1.1.1.3.2. Conteo de OEPara el conteo de operaciones elementales de método del búsqueda secuencial en su mejor caso se define tal y como se planteó en su definición y dicho conteo será subrayado con color rojo todas y cada una de las OE que se hagan en el algoritmo implementado en lenguaje Java.

Nota: Las OE que salgan subrayadas son las que te contaran en cuenta para dicho conteo, si una instrucción sale doblemente subrayada es por sé hacer dos OE en ella.

línea OE1 42 33 1Total 8 OE

1.1.1.4. Peor Casos

1.1.1.4.1. DefiniciónPara el peor caso del método de búsqueda secuencia se puede presentar en dos ocasiones que el elemento que deseamos hallar esté en la última posición del vector o que dicho elemento no ese encuentre en el arreglo; en ambos casos el método tiene que recorrer todos las posiciones del arreglo es decir; desde la primer hasta el último índice.

Ejemplo: queremos buscar a 10:

Datos 1 2 4 5 6 7 8 9 9 10Índice

0 1 2 3 4 5 6 7 8 9

1.1.1.4.2. Conteo de OEPara el conteo de operaciones elementales en este caso se realiza de manera similar al caso anterior.

Para este hacer una prueba a tomaremos el caso en que el elemento a buscar se encuentre la última casilla de vector.

7


Las OE que se realizan en las líneas 1 y 2 se ejecutan n veces entonces se multiplican por n siendo n el tamaño de los datos de entrada. La OE de la línea 3 solo se realiza unas ves y es cuando se encuentra el elemento para este caso en la última posición.

1.1.1.5. Pasos promedio El caso promedio o también llamado caso aleatorios no se puede hacer un coteo de operaciones elementales exacto ya que el elemento a encontrar puede estar el cualquier índice del vector; entonces para dar solución a este altercado se divide el número datos de entradas del vector entre dos

vector[N/2]

1.1.1.6. Grafica Mejor casos vs Peor caso

línea OE1 4n2 3N3 1Total 7n+1 OE

8

1.1.1.7. Te

oría vs Practica del conteo de OE

Datos De Entrada = 100,000Caso Teoría Practica (Programa)Mejor 8 0 utPeor (7*n)+1=700,001 4 ut

Conclusiones: De acuerdo con los pruebas realizadas entre la teoría de conteo de operaciones elementales y el tiempo de ejecución del mismo algoritmo implementado en un programa en lenguaje Java; puedo concluir que de la teoría y práctica arrojan resultados totalmente distintos y se puede apreciar el tabla de la (teoría vs práctica)

1.1.2. Búsqueda Binaria

1.1.2.1. Definición El método de búsqueda binaria es un excelente forma de buscar elementos dentro de un vector, este algoritmos de búsqueda requiere que le vector se encuentre ordenado previamente, se llama de búsqueda binaria por que el algoritmo divide en dos y compra los elementos que se encuentren en la posición

de centro de arreglo. Esta búsqueda utiliza un método de “divide y vencerás” para localizar el valor deseado

1.1.2.2. Código

0 1 2 3 4 5 6 7 8 9 100

1

2

3

4

5

6

7

8

9

10

OE Mejor CasoOE Peor Caso

9

1.1.2.3. Mejor Caso

1.1.2.3.1. DefiniciónPara el conteo de operaciones elementales del método de la búsqueda binaria en su mejor caso se define de la siguiente manera; lo ideal es que en el datos se halle en la posición centro del vector


10

1.1.2.3.2. Conteo de OEHaciendo las operaciones de las primeras 5 filas con un vector de 10 posiciones quedan de la siguiente manera

K=6;

cen = 9/2 =4,5 peso como la variable cen es de tipo entero no se toman los decimales entonces cen =4

Datos 1 2 4 5 6 7 8 9 9 10Índice

0 1 2 3 4 5 6 7 8 9

Exactamente se van a cumplir la OE que están subrayadas en la imagen anterior

Línea 0E1 12 13 24 35 410 211 1Totales OE 140E

11

1.1.2.4. Peor Caso

1.1.2.4.1. DefiniciónLa definición de peor casos para el algoritmo de búsqueda binaria se presenta cuando el elemento al que queramos encontrar no se encuentre almacenado o este en algunos de los dos extremos la lista; esto conlleva a que el método dividirá el vector varias veces y hará comparaciones en vano hasta la última iteración del ciclo while.

1.1.2.4.2. Información para el peor caso

(UChile)

(UChile)

12

1.1.2.4.3. Conteo de OETotal OE=19¿¿

1.1.2.4.4. Teoría vs Practica Del Conteo OE

Datos De Entrada = 100,000Caso Teoría Practica (Programa)Mejor 14 0 utPeor 19¿¿ =325.58 0 ut

Según los resultados del tiempo de ejecución en el mejor caso y el peor caso con el número de entrada = 100,00 No logra que programa calcule ninguna unidad de tiempo, eso se debe a la misma eficiencia del algoritmo de búsqueda

13

1.1.2.4.5. Grafica Mejor Vs Peor Caso(Tiempo Ejecucion)

0 200000 400000 600000 800000 1000000 12000000

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Mejor CasoPeor Caso

Podemos observar que las líneas que presentan el mejor y el peor caso para el algoritmo de búsqueda binaria toma un valor de 0 ut esto sucede porque dicho algoritmos no depende de los todos de entrada simpe y cuando el vector este ordenado.

Nota: en tiempo de ejecución fue calculado con diferentes números de datos de entrada, probado en el mismo programa, el mimos equipo y en situaciones muy parecidas en cambios casos.

1.1.3. Método Transponer

1.1.3.1. Definición Transpuesta de una matriz m x n, es la matriz n x m cuyas columnas son los renglones de A en el mismo orden. (wikibooks)

En otras palabras se intercambia las los valores de las columnas por los de las filas

una matriz Ejemplo: sea B la matriz original y sea BT la matriz transpuesta

14

1.1.3.2. Código

Primera forma

Segunda forma

1.1.3.3. Evaluar casos Como se definió anterior mente el método transponer (); transpone los datos de una matriz ojo como en el cuerpo de ese método no tienes instrucciones de condiciones if entonces esto quiere decir que en el algoritmos de trasposición NO aplican los casos y estos son (mejor caso), (caso promedio) y (peor caso) , la explicación de ellos es que el único objetivo de método es transponer la matriz dependiendo entonces del N que es el número de datos de entrada que en esta implementación hecha en lenguaje JAVA, N= matriz.length.

Conclusión: el grada de complejidad de penderá de numero de OE del métodos por el tamaño de datos de entrada.

15

1.1.3.4. Grados de complejidad

1.1.3.4.1. Primera forma Primera implementación de este método más eficiente que la segunda forma. La diferencia de estos dos métodos está en la variable j, miremos la codificación del for interno “for (int j = i+1; j < matriz.length; j++) {” notamos que la variable j toma el mismo valor i pero se le suma 1 esto quiere decir que j siempre a tomar tener 1 valor más que i en 1 y realizar por cada un vez menos por cada iteración del ciclo externo.

Línea OE1 5(N-1)2 5 (N-1)*(N-1)3 3(N-1) *(N-1)4 5(N-1) *(N-1)5 3(N-1) *(N-1)Total OE=16N2−(27∗N )−21

1.1.3.4.2. Segunda Forma Este algoritmos es más ineficiente con respecto al anterior su explicación es la siguiente la imagen de código exenten for anidados entonces se presenta la siguiente situación el for el extremo se ejecuta (N−1 )veces y le interno se

ejecutara (N−1¿¿2

Conteo de OE:

Línea OE1 5N2 5N2

3 4N2

4 7N2

5 4N2

Total OE=20¿

1.1.3.4.3. Teoría vs Practica conteo OEDatos De Entrada = 500Método Teoría Practica (Programa)Primero 3,986,479 7 utSegundo 4,982,515 13 ut

Conclusión: Si comparamos la teoría con la práctica al igual que el método de búsqueda secuencial nos podemos apreciar que los resultados son totalmente diferentes.

16

Pero si vamos un poco más allá de la situación y comparamos los resultados entre los dos métodos (primero y segundo) nos damos cuenta que tanto en operaciones elementales como en tiempo de ejecución el método 1 es más eficiente que el 2 con el mismo número de datos de entrada y solucionado el mismo problema(transponer una matriz).

Mi observación: La opción de modificar el algoritmo original fue algo que me nació desde un principio y pude notar que hacer ciertos cambios en las operaciones de un algoritmo se ve reflejado en las operaciones elementales y en tiempo de ejecución.

1.1.3.4.4. Grafica Primer Método Vs Segundo Método

0 200 400 600 800 1000 12000

5

10

15

20

25

30

35

40

1r Metodo2do Metodo

Apreciando el comportamiento de las curvas notamos que representa al segundo método tiene un crecimiento mayor en tiempo de ejecución con los el mismo número de datos de entrada, probado en el mismo programa, el mimos equipo y en situaciones muy parecidas al primer método.

Analisis busquedas !

Documents

Transcript of Analisis busquedas !