jueves, 21 de julio de 2016
miércoles, 20 de julio de 2016
domingo, 10 de julio de 2016
Algoritmos
REPÚBLICA BOLIVARIANA DE VENEZUELA
UNIVERSIDAD PEDAGÓGICA EXPERIMENTAL
LIBERTADOR
INSTITUTO DE MEJORAMIENTO PROFESIONAL
DEL MAGISTERIO
EXTENSIÓN SAN FELIPE
ALGORITMOS
Autoras:
Cabrera Yormary
De Andrade, Nelia
Osorio, Ysbel
Soto, Heilin
Asignatura:
Matemática Discreta
Especialidad Informática
Cohorte 2015
Profesor:
Aponte José
Julio, 2016
ALGORITMO
Un
Algoritmo, se puede definir como una secuencia de instrucciones que representan
un modelo de solución para determinado tipo de problemas. O bien como un
conjunto de instrucciones que realizadas en orden conducen a obtener la
solución de un problema. Por lo tanto podemos decir que es un conjunto ordenado
y finito de pasos que nos permite solucionar un problema.
Los
algoritmos son independientes de los lenguajes de programación. En cada
problema el algoritmo puede escribirse y luego ejecutarse en un lenguaje de
diferente programación. El algoritmo es la infraestructura de cualquier
solución, escrita luego en cualquier lenguaje de programación.
Un
programa es una serie de instrucciones ordenadas, codificadas en lenguaje de
programación que expresa un algoritmo y que puede ser ejecutado en un
computador.
CARACTERÍSTICAS
DE UN ALGORITMO
1. Debe
ser Preciso, porque cada uno de sus pasos debe indicar de manera precisa e inequívoca
que se debe hacer.
2. Debe
ser Finito, porque un algoritmo debe tener un número limitado de pasos.
3. Debe
ser Definido, porque debe producir los mismos resultados para las mismas
condiciones de entrada.
4. Puede
tener cero o más elementos de entrada.
5. Debe
producir un resultado. Los datos de salida serán los resultados de efectuar las
instrucciones.
PARTES DE UN ALGORITMO
§ Entrada
de datos, son los datos necesarios que el algoritmo necesita para ser
ejecutado.
§ Proceso,
es la secuencia de pasos para ejecutar el algoritmo.
§ Salida
de resultados, son los datos obtenidos después de la ejecución del algoritmo.
Representación gráfica de un algoritmo.
ALGORITMOS DE ORDENAMIENTO
La
ordenación o clasificación de datos (sort, en inglés) es una operación
consistente en disponer un conjunto de datos en algún determinado orden con
respecto a uno de los campos de elementos del conjunto. Por ejemplo, cada
elemento del conjunto de datos de una guía telefónica tiene un campo nombre, un
campo dirección y un campo número de teléfono; la guía telefónica está dispuesta
en orden alfabético de nombres; los elementos numéricos se pueden ordenar en
orden creciente o decreciente de acuerdo al valor numérico del elemento. En
terminología de ordenación, el elemento por el cual está ordenado un conjunto
de datos (o se está buscando) se denomina clave.
Una
colección de datos (estructura) puede ser almacenada en un archivo, un array
(vector o tabla), un array de registros, una lista enlazada o un árbol. Cuando
los datos están almacenados en un array, una lista enlazada o un árbol, se
denomina ordenación interna. Si los datos están almacenados en un archivo, el
proceso de ordenación se llama ordenación externa.
Una
lista se dice que está ordenada por la clave k si la lista está en orden
ascendente o descendente con respecto a esta clave. La lista se dice que está
en orden ascendente si:
i <
j implica que k[i] <= k[j]
y se
dice que está en orden descendente si:
i >
j implica que k[i] <= k[j]
Por
ejemplo, para una guía telefónica, la lista está clasificada en orden
ascendente por el campo clave k, donde k[i] es el nombre del abonado
(apellidos, nombre).
4 5 14 21 32 45 Orden ascendente
75 70
35 16 14
12 Orden descendente
Métodos de ordenación
Los métodos de ordenación se suelen dividir en
dos grandes grupos:
Directos: intercambio, inserción, selección y burbuja
Indirectos (avanzados): Shell y
Quicksort.
En el
caso de listas pequeñas, los métodos directos se muestran eficientes, sobre
todo porque los algoritmos son sencillos; su uso es muy frecuente. Sin embargo,
en listas grandes estos métodos se muestran ineficaces y es preciso recurrir a
los métodos avanzados.
Ordenación por intercambio.
El
algoritmo de ordenación tal vez más sencillo sea el denominado de intercambio
que ordena los elementos de una lista en orden ascendente. Este algoritmo se
basa en la lectura sucesiva de la lista a ordenar, comparando el elemento
inferior de la lista con los restantes y efectuando intercambio de posiciones
cuando el orden resultante de la comparación no sea el correcto.
El
algoritmo se ilustra con la lista original 8, 4, 6, 2 que ha de convertirse en
la lista ordenada
2, 4,
6, 8. El algoritmo realiza n − 1 pasadas (3 en el ejemplo), siendo n el número
de elementos, y ejecuta las siguientes operaciones.
Pasada
0
El
elemento de índice 0 (a[0]) se compara con cada elemento posterior de la lista
de índices 1, 2 y 3. En cada comparación se comprueba si el elemento siguiente
es más pequeño que el elemento de índice 0, en ese caso se intercambian.
Después de terminar todas las comparaciones, el elemento más pequeño se
localiza en el índice 0.
Pasada
1
El
elemento más pequeño ya está localizado en el índice 0, y se considera la
sublista restante 8, 6, 4. El algoritmo continúa comparando el elemento de
índice 1 con los elementos posteriores de índices 2 y 3. Por cada comparación,
si el elemento mayor está en el índice 1 se intercambian los elementos. Después
de hacer todas las comparaciones, el segundo elemento más pequeño de la lista
se almacena en el índice 1.
Pasada
2
La
sublista a considerar ahora es 8, 6 ya que 2, 4 está ordenada. Una comparación
única se produce entre los dos elementos de la sublista.
El
método ordIntercambio utiliza dos bucles anidados. Suponiendo que la lista es
de tamaño n, el rango del bucle externo irá desde el índice 0 hasta n − 2. Por
cada índice i, se comparan los elementos posteriores de índices j = i + 1, i +
2, ..., n − 1. El intercambio (swap) de los elementos a[i],a[j] se realiza en
un bloque que utiliza el algoritmo siguiente:
aux = a[i];
a[i] = a[j];
a[j]= aux ;
Método de inserción.
Este
método toma cada elemento del arreglo para ser ordenado y lo compara con los
que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si
resulta que el elemento con el que se está comparando es mayor que el elemento
a ordenar, se recorre hacia la siguiente posición superior. Si por el
contrario, resulta que el elemento con el que se está comparando es menor que
el elemento a ordenar, se detiene el proceso de comparación pues se encontró
que el elemento ya está ordenado y se coloca en su posición (que es la
siguiente a la del último número con el que se comparó).
Procedimiento Insertion Sort: Este procedimiento
recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus
elementos hasta dejarlos ordenados de menor a mayor. N representa el número de
elementos que contiene a[].
paso 1:
[Para cada pos. del arreglo] For i <- 2 to N do
paso 2:
[Inicializa v y j] v <- a[i]
j <-
i.
paso 3:
[Compara v con los anteriores] While a[j-1] > v AND j>1 do
paso 4:
[Recorre los datos mayores] Set a[j] <- a[j-1],
paso 5:
[Decrementa j] set j <- j-1.
paso 5:
[Inserta v en su posición] Set a[j] <- v.
paso 6:
[Fin] End.
Ejemplo:
Si el
arreglo a ordenar es a =
['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'], el algoritmo va
a recorrer el arreglo de izquierda a derecha. Primero toma el segundo dato 's'
y lo asigna a v y i toma el valor de la posición actual de v.
Luego
compara esta 's' con lo que hay en la posición j-1, es decir, con 'a'. Debido a
que 's' no es menor que 'a' no sucede nada y avanza i.
Ahora v
toma el valor 'o' y lo compara con 's', como es menor recorre a la 's' a la
posición de la 'o'; decrementa j, la cual ahora tiene la posición en dónde
estaba la 's'; compara a 'o' con a[j-1] , es decir, con 'a'. Como no es menor
que la 'a' sale del for y pone la 'o' en la posición a[j]. El resultado hasta
este punto es el arreglo siguiente: a = ['a','o','s','r',....]
Así se
continúa y el resultado final es el arreglo ordenado :
a =
['a','a','e','e','g','i','l','m','n','o','p','r','s','t','x']
El
método de ordenación por inserción es similar al proceso típico de ordenar
tarjetas de nombres (cartas de una baraja) por orden alfabético, que consiste
en insertar un nombre en su posición correcta dentro de una lista o archivo que
ya está ordenado. Así el proceso en el caso de la lista de enteros
A = 50,
20, 40, 80, 30.
El
algoritmo correspondiente a la ordenación por inserción contempla los
siguientes pasos:
1. El
primer elemento A[0] se considera ordenado; es decir, la lista inicial consta
de un elemento.
2. Se
inserta A[1] en la posición correcta, delante o detrás de A[0], dependiendo de
que sea menor o mayor.
3. Por
cada bucle o iteración i (desde i=1 hasta n-1) se explora la sublista A[i-1] .
. A[0] buscando la posición correcta de inserción; a la vez se mueve hacia
abajo (a la derecha en la sublista) una posición todos los elementos mayores
que el elemento a insertar A[i], para dejar vacía esa posición.
4. Insertar
el elemento a la posición correcta.
Método de selección.
El
método de ordenamiento por selección consiste en encontrar el menor de todos
los elementos del arreglo e intercambiarlo con el que está en la primera
posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenar todo
el arreglo.
Procedimiento Selection Sort
paso 1:
[Para cada pos. del arreglo] For i <- 1 to N do
paso 2:
[Inicializa la pos. del menor] menor <- i
paso 3:
[Recorre todo el arreglo] For j <- i+1 to N do
paso 4:
[Si a[j] es menor] If a[j] < a[menor] then
paso 5:
[Reasigna el apuntador al menor] min = j
paso 6:
[Intercambia los datos de la pos.
min y
posición i] Swap(a, min, j).
paso 7:
[Fin] End.
Ejemplo:
El
arreglo a ordenar es a =
['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'].
Se
empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso
el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio.
Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'.
Esta se
intercambia con el dato que está en la segunda posición, la 's', quedando el
arreglo así después de dos recorridos: a = ['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e'].
El
siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la
cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le
sigue la segunda 's', la cual es intercambiada con la 'r'.
El
arreglo ahora se ve de la siguiente manera: a =
['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r'].
De esta
manera se va buscando el elemento que debe ir en la siguiente posición hasta
ordenar todo el arreglo.
El
número de comparaciones que realiza este algoritmo es :
Para el
primer elemento se comparan n-1 datos, en general para el elemento i-ésimo se
hacen n-i comparaciones, por lo tanto, el total de comparaciones es:
la
sumatoria para i de 1 a n-1 (n-i) = 1/2 n (n-1).
Considérese
el algoritmo para ordenar un array A de enteros en orden ascendente, es decir,
del número más pequeño al mayor. Es decir, si el array A tiene n elementos, se
trata de ordenar los valores del array de modo que el dato contenido en A[0]
sea el valor más pequeño, el valor almacenado en A[1] el siguiente más pequeño,
y así hasta A[n-1], que ha de contener el elemento de mayor valor. El algoritmo
se apoya en sucesivas pasadas que intercambian el elemento más pequeño
sucesivamente con el primer elemento de la lista, A[0] en la primera pasada. En
síntesis, se busca el elemento más pequeño de la lista y se intercambia con
A[0], primer elemento de la lista.
A[0]
A[1] A[2].... A[n-1]
Después
de terminar esta primera pasada, el frente de la lista está ordenado y el resto
de la lista
A[1],
A[2]...A[n-1] permanece desordenado. La siguiente pasada busca en esta lista
desordenada y selecciona el elemento más pequeño, que se almacena entonces en
la posición A[1]. De este modo los elementos A[0] y A[1] están ordenados y la
sublista A[2], A[3]...A[n-1] desordenada; entonces, se selecciona el elemento
más pequeño y se intercambia con A[2]. El proceso continúa n − 1 pasadas y en
ese momento la lista desordenada se reduce a un elemento (el mayor de la lista)
y el array completo ha quedado ordenado.
Un
ejemplo práctico ayudará a la comprensión del algoritmo. Consideremos un array
A con 5 valores enteros 51, 21, 39, 80, 36:
Como se
puede observar, Los pasos del algoritmo son:
1. Seleccionar
el elemento más pequeño de la lista A; intercambiarlo con el primer elemento
A[0]. Ahora la entrada más pequeña está en la primera posición del vector.
2. Considerar
las posiciones de la lista A[1], A[2], A[3]..., seleccionar el elemento más
pequeño e intercambiarlo con A[1]. Ahora las dos primeras entradas de A están
en orden.
3. Continuar
este proceso encontrando o seleccionando el elemento más pequeño de los
restantes elementos de la lista, intercambiándolos adecuadamente.
Método burbuja.
El
bubble sort, también conocido como ordenamiento burbuja, funciona de la siguiente
manera: Se recorre el arreglo intercambiando los elementos adyacentes que estén
desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios.
Prácticamente lo que hace es tomar el elemento mayor y lo va recorriendo de
posición en posición hasta ponerlo en su lugar.
Procedimiento Bubble Sort
paso 1:
[Inicializa i al final de arreglo] For i <- N down to 1 do
paso 2:
[Inicia desde la segunda pos.] For j <- 2 to i do
paso 4:
[Si a[j-1] es mayor que el que le sigue] If a[j-1] < a[j] then
paso 5:
[Los intercambia] Swap(a, j-1, j).
paso 7:
[Fin] End.
Tiempo
de ejecución del algoritmo burbuja:
1. Para el mejor caso (un paso) O(n)
2. Peor caso n(n-1)/2
3. Promedio O(n2)
El
método de ordenación por burbuja es el más conocido y popular entre estudiantes
y aprendices de programación, por su facilidad de comprensión y programación;
por el contrario, es el menos eficiente y por ello, normalmente, se aprende su
técnica pero no suele utilizarse.
La
técnica utilizada se denomina ordenación por burbuja u ordenación por
hundimiento debido a que los valores más pequeños «burbujean» gradualmente
(suben) hacia la cima o parte superior del array de modo similar a como suben
las burbujas en el agua, mientras que los valores mayores se hunden en la parte
inferior del array. La técnica consiste en hacer varias pasadas a través del
array. En cada pasada, se comparan parejas sucesivas de elementos. Si una
pareja está en orden creciente (o los valores son idénticos), se dejan los valores
como están. Si una pareja está en orden decreciente, sus valores se
intercambian en el array.
Las
etapas del algoritmo son:
§ En la
pasada 0 se comparan elementos adyacentes:
§ (A[0],A[1]),(A[1],A[2]),(A[2],A[3]),...(A[n-2],A[n-1])
§ Se
realizan n − 1 comparaciones, por cada pareja (A[i],A[i+1]) se intercambian los
valores si A[i+1] < A[i]. Al final de la pasada, el elemento mayor de la
lista está situado en A[n-1].
§ En la
pasada 1 se realizan las mismas comparaciones e intercambios, terminando con el
elemento segundo mayor valor en A[n-2].
§ El
proceso termina con la pasada n − 1, en la que el elemento más pequeño se
almacena en A[0].
El algoritmo tiene una mejora inmediata, el
proceso de ordenación puede terminar en la pasada n − 1, o bien antes, si en
una pasada no se produce intercambio alguno entre elementos del vector es
porque ya está ordenado, entonces no es necesario más pasadas.
El ejemplo siguiente ilustra el funcionamiento
del algoritmo de la burbuja con un array de 5 elementos (A = 50, 20, 40, 80, 30),
donde se introduce una variable interruptor para detectar si se ha producido
intercambio en la pasada.
En
consecuencia, el algoritmo de ordenación de burbuja mejorado contempla dos
bucles anidados: el bucle externo controla la cantidad de pasadas (al principio
de la primera pasada todavía no se ha producido ningún intercambio, por tanto
la variable interruptor se pone a valor falso (0); el bucle interno controla
cada pasada individualmente y cuando se produce un intercambio, cambia el valor
de interruptor a verdadero (1).
El
algoritmo terminará, bien cuando se termine la última pasada (n − 1) o bien
cuando el valor del interruptor sea falso (0), es decir, no se haya hecho
ningún intercambio. La condición para realizar una nueva pasada se define en la
expresión lógica: (pasada < n-1) && interruptor
Codificación en C del algoritmo de la burbuja
La
función ordBurbuja() implementa el algoritmo de ordenación de la burbuja; tiene
dos argumentos, el array que se va a ordenar crecientemente, y el número de
elementos n. En la codificación se supone que los elementos son de tipo entero
largo.
void ordBurbuja (long a[], int n)
{
int
interruptor = 1;
int
pasada, j;
for
(pasada = 0; pasada < n-1 && interruptor; pasada++)
{
/*
bucle externo controla la cantidad de pasadas */
interruptor
= 0;
for (j
= 0; j < n-pasada-1; j++)
if
(a[j] > a[j+1])
{
/*
elementos desordenados, es necesario intercambio */
long aux;
interruptor = 1;
aux = a[j];
a[j] =
a[j+1];
a[j+1]
= aux;
}
}
Método de shell.
Ordenamiento
de disminución incremental. Nombrado así debido a su inventor Donald Shell.
Ordena subgrupos de elementos separados K unidades (respecto de su posición en
el arreglo) del arreglo original. El valor K es llamado incremento.
Después
de que los primeros K subgrupos han sido ordenados (generalmente utilizando
INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es
de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los
subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más
pequeño de K.
Eventualmente
el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el
arreglo ya casi ordenado.
Al
principio del proceso se escoge la secuencia de decrecimiento de incrementos;
el último valor debe ser 1.
"Es
como hacer un ordenamiento de burbuja pero comparando e intercambiando
elementos."
Cuando
el incremento toma un valor de 1, todos los elementos pasan a formar parte del
subgrupo y se aplica inserción directa.
El
método se basa en tomar como salto N/2 (siendo N el número de elementos) y
luego se va reduciendo a la mitad en cada repetición hasta que el salto o
distancia vale 1.
Ejemplo:
Obtener
las secuencias parciales del vector al aplicar el método Shell para ordenar en
orden creciente la lista:
6 1 5 2 3 4 0
El
número de elementos que tiene la lista es 6, por lo que el salto inicial es 6/2
= 3. La siguiente tabla muestra el número de recorridos realizados en la lista
con los saltos correspondiente.
Los
pasos a seguir por el algoritmo para una lista de n elementos son:
1.
Dividir la lista original en n/2 grupos de dos, considerando un incremento o
salto entre los elementos de n/2.
2.
Clarificar cada grupo por separado, comparando las parejas de elementos, y si
no están ordenados, se intercambian.
3. Se
divide ahora la lista en la mitad de grupos (n/4), con un incremento o salto
entre los elementos también mitad (n/4), y nuevamente se clasifica cada grupo
por separado.
4. Así
sucesivamente, se sigue dividiendo la lista en la mitad de grupos que en el
recorrido anterior con un incremento o salto decreciente en la mitad que el
salto anterior, y luego clasificando cada grupo por separado.
5. El
algoritmo termina cuando se consigue que el tamaño del salto es 1.
Por
consiguiente, los recorridos por la lista está condicionados por el bucle,
intervalo v n / 2
mientras (intervalo > 0) hacer
Para
dividir la lista en grupos y clasificar cada grupo se anida este código,
desde i v (intervalo + 1) hasta n hacer
j v i - intervalo
mientras (j > 0) hacer
k v j + intervalo
si (a[j] <= a[k]) entonces
j v − 1
sino
Intercambio (a[j], a[k]);
j v j - intervalo
fin_si
fin_mientras
fin_desde
En el
código anterior se observa que se comparan pares de elementos indexados por j y
k, (a[j],a[k]), separados por un salto, intervalo. Así, si n = 8 el primer
valor de intervalo = 4, y los índices i =5, j =1, k =6. Los siguientes valores
de los índices son i = 6, j = 2, k = 7, y así hasta recorrer la lista.
Para
realizar un nuevo recorrido de la lista con la mitad de grupos, el intervalo se
hace la mitad: intervalo v intervalo / 2 así se repiten los recorridos por la
lista, mientras intervalo > 0.
Algoritmo de Quicksort (Ordenación rápida)
El
algoritmo fundamental es el siguiente:
§ Elegir
un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
§ Resituar
los demás elementos de la lista a cada lado del pivote, de manera que a un lado
queden todos los menores que él, y al otro los mayores. Los elementos iguales
al pivote pueden ser colocados tanto a su derecha como a su izquierda,
dependiendo de la implementación deseada. En este momento, el pivote ocupa
exactamente el lugar que le corresponderá en la lista ordenada.
§ La
lista queda separada en dos sublistas, una formada por los elementos a la
izquierda del pivote, y otra por los elementos a su derecha.
§ Repetir
este proceso de forma recursiva para cada sublista mientras éstas contengan más
de un elemento. Una vez terminado este proceso todos los elementos estarán
ordenados.
Como se
puede suponer, la eficiencia del algoritmo depende de la posición en la que
termine el pivote elegido.
•
En el mejor caso, el pivote termina en el centro
de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el
orden de complejidad del algoritmo es O(n•log n).
•
En el peor caso, el pivote termina en un extremo
de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El
peor caso dependerá de la implementación del algoritmo, aunque habitualmente
ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero
principalmente depende del pivote, si por ejemplo el algoritmo implementado
toma como pivote siempre el primer elemento del array, y el array que le
pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que
es ineficiente.
•
En el caso promedio, el orden es O(n•log n).
No es
extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se
centren en la elección del pivote.
Ejemplo:
Se
ordena una lista de números enteros aplicando el algoritmo quicksort, como
pivote se elige el primer elemento de la lista.
ALGORITMOS DE BUSQUEDA
Con
frecuencia el programador trabajara con grandes cantidades de información
almacenada en arreglos. Podrá ser necesario determinar si algún arreglo con
tiene un valor que sea igual a cierto valor clave.
El
proceso para encontrar un elemento particular en un arreglo se llama búsqueda.
Estudiaremos dos técnicas de búsqueda: una técnica simple llamada búsqueda
lineal y una más eficiente llamada búsqueda binaria.
Búsqueda
lineal
La búsqueda
lineal compara los elementos del array con la clave de búsqueda hasta que
encuentra el elemento o bien hasta que se determina que no se encuentra.
int
busqueda lineal (int A[], int clave, int n)
f
for(int
i=0;i<n;i++)
if
(A[i]==clave) return i;
3
return -1;
g
Este método
funciona bien con arreglos pequeños y con los no ordenados. En arreglos grandes
u ordenados conviene aplicar la búsqueda binaria que es más eficiente.
Búsqueda binaria
Dados
un entero X y un array A de n enteros que se encuentran ordenados y en memoria,
encontrar un i talque A[i] == X o retornar 0 si X no se encuentra en el array
(consideramos los elementos del array de 1 a N.
La
estrategia consiste en comparar X con el elemento del medio del array, si es
igual entonces encontramos el elemento, sino, cuando X es menor que el elemento
del medio aplicamos la misma estrategia al array a la izquierda del elemento
del medio y si X es mayor que el elemento del medio aplicamos la misma
estrategia al array a la derecha de dicho elemento.
Para
simplificar el código A[0]=X.
int
busqueda binaria(int A[],int X,int n)
f
int izq=1,medio,der=n;
A[0]=X;
do
f
medio = (izq+der) / 2;
if(izq > der)
medio=0;
else if A[medio] < X
izq = medio +1;
else der=medio-1;
g
while (A[medio] != X);
return medio;
g
COMPLEJIDAD ALGORÍTMICA
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.
La
complejidad de un algoritmo se mide de
acuerdo al tiempo (que se demora en ejecutarse el algoritmo) y espacio (se
refiere a cuanta memoria ocupara para su ejecución)
Complejidad
del peor caso: indica cuantas operaciones tienen que
realizar un algoritmo para garantizar que producirán una solución.
Complejidad
del caso promedio: se busca el promedio de operaciones
realizadas para solucionar un problema considerando todas las posibles entradas
con un tamaño determinado.
Complejidad
en el mejor de los casos: mínimos procesos para llegar a una
solución.
Orden
de complejidad
La complejidad de un
algoritmo deberá estar relacionada con el número de operaciones elementales
necesarias (asignaciones, comparaciones, sumas, restas, multiplicaciones,
divisiones, etc.) para resolver un problema dado. El número de estas
operaciones dependerá de los datos de entrada y éstos pueden dar lugar desde
una solución especialmente favorable hasta una especialmente costosa.
Por ejemplo
En la búsqueda secuencial de un
vector ordenado, si el valor buscado es el menor lo obtendremos con muy pocas
operaciones, sin embargo si buscamos el último, la solución supondrá recorrer
todo el vector. Por ello se habla del mejor, del peor caso y del caso medio.
Para el peor caso de un algoritmo, expresaremos la función que mide el número
de operaciones según el tamaño del problema como f(n), que tomaremos como
medida aproximada de la eficiencia.
Diremos
que la complejidad del algoritmo es del orden de g(n) (lo representaremos por
O(g(n)) ) si existe un n0 tal que, para todo valor de n ≥ n0 , existe una
constante C tal que |f(n)| ≤ C |g(n)|. Con esta definición, si f(n) es un
polinomio de grado k, el algoritmo correspondiente tendrá una complejidad
O(nk), independientemente de cuáles sean los coeficientes y términos de menor
grado del polinomio. De esta forma se formaliza la idea de que dos algoritmos
de distinta eficiencia tengan la misma complejidad. En el caso de la figura
7.3, la complejidad de los algoritmos es de O(n) y O(2n) respectivamente.
Si un algoritmo tiene una
complejidad de O(nk), se dice que es polinomial2 (en el caso de k=1 se le llama
lineal, para k=2 cuadrático y para k=3 cúbico); el resto de algoritmos se
conocen como no-polinomiales. La siguiente tabla muestra el tiempo que tardaría
un computador en realizar f(n) operaciones, para distintas funciones f y
distintos valores de n, suponiendo que realizase un millón de operaciones por
segundo.
Complejidad
de la búsqueda secuencial
La complejidad de la búsqueda
secuencial diferencia entre el comportamiento en el caso peor y mejor. El mejor
caso se encuentra cuando aparece una coincidencia en el primer elemento de la
lista y en ese caso el tiempo de ejecución es O(1). El caso peor se produce
cuando el elemento no está en la lista o se encuentra al final de la lista.
Esto requiere buscar en todos los n términos, lo que implica una complejidad de
O(n).
El caso medio requiere un poco de
razonamiento probabilista. Para el caso de una lista aleatoria es probable que
una coincidencia ocurra en cualquier posición. Después de la ejecución de un
número grande de búsquedas, la posición media para una coincidencia es el
elemento central n/2. El elemento central ocurre después de n/2 comparaciones,
que define el coste esperado de la búsqueda. Por esta razón, se dice que la
prestación media de la búsqueda secuencial es O(n).
|
COMPLEJIDAD
|
TERMINOLOGIA
|
|
O (1)
|
Complejidad constante
|
|
O (n 2)
|
Complejidad cuadrática
|
|
O (log n)
|
Complejidad logarítmica
|
|
O (n)
|
Complejidad lineal
|
|
O (n log n)
|
Complejidad casi - lineal
|
|
O (n^b)
|
Complejidad polinomica
|
|
O (b^n)
|
Complejidad exponencial
|
|
O (n!)
|
Complejidad factorial
|
Suscribirse a:
Entradas (Atom)