Estructura de datos :filas y colas

PRECONDICIÓN Y POSTCONDICIÓN
Si A es la precondición, B la postcondición y P el
algoritmo, entonces la notación
{A} P {B}
Representa la especificación de P, y se lee:

Si P comienza su ejecución en un estado descrito por
la precondición A, P termina, y lo hace en un estado
descrito por B.

PRECONDICIÓN Y POSTCONDICIÓN
Ejemplo:
Si se quiere especificar un algoritmo para hallar elcociente por defecto y el módulo de dos enteros:
Entrada:
a: dividendo
b: divisor
Salida:
q: cociente
r: módulo
Podríamos especificar el algoritmo con la siguiente
precondición y postcondición
Precondición A { (a ≥ 0) (b > 0) }
Postcondición B { (a = b * q + r) (r ≥ 0) (r < b) }

COMPLEJIDAD DE LOS ALGORITMOS
Para comparar dos algoritmos que solucionan el mismo
problema es necesarioaportar criterios que midan la
eficiencia de ambos.
Supongamos que M es un algoritmo y que n es el
tamaño de los datos de entrada. El tiempo de
ejecución y el espacio utilizados por M son los
parámetros principales que miden la eficiencia de M.
El tiempo suele medirse contando el número de
operaciones clave realizadas. (Por ejemplo, el
número de comparaciones realizadas en una
búsqueda uordenación). El tiempo empleado en otras
operaciones no clave es menor o a lo sumo
proporcional al empleado por éstas.

COMPLEJIDAD DE LOS ALGORITMOS
El espacio es evaluado contando el máximo de memoria
necesaria por el algoritmo.
La complejidad de un algoritmo M es una función f(n)
que da el tiempo y/o el espacio de almacenamiento
necesario en la ejecución del algoritmo, en función
deltamaño de los datos de entrada n. Con frecuencia
el espacio de almacenamiento necesario es un
múltiplo de n. Por ello, el termino “complejidad” se
referirá siempre al tiempo de ejecución.
f(n) se va definir como el tiempo de ejecución del
PEOR CASO, es decir, el máximo valor del tiempo
de ejecución para entradas de tamaño n.

COMPLEJIDAD DE LOS ALGORITMOS
Rango de crecimiento; notaciónasintótica O
Sea M un algoritmo y n el tamaño de la entrada. La
complejidad f(n) crecerá siempre al aumentar n. Es
conveniente estudiar como crece f(n) al hacerlo n.
Esto se realiza normalmente mediante la
comparación de f(n) con una de las funciones
estándar tales como:
log2 n,

n,

n log2 n,

n2,

n3,

2n

Las funciones han sido ordenadas según el rango de
crecimiento de lasmismas.

COMPLEJIDAD DE LOS ALGORITMOS
Rango de crecimiento; notación asintótica O

Rango de crecimiento de funciones estándar:
n \
5
10
100
1000

log2 n
3
4
7
10

n
n log2 n
5
15
10
40
100
700
103
104

n2
25
100
104
106

n3
125
103
106
109

2n
32
103
1030
10300

COMPLEJIDAD DE LOS ALGORITMOS
Rango de crecimiento; notación asintótica O
Una forma decomparar la función f(n) con las estándar
es mediante la notación O, definida como sigue:
Sean f(n) y g(n) dos funciones de enteros positivos que
tienen la característica de que f(n) está acotada por un
múltiplo de g(n) para casi todos los valores de n. Es
decir, supongamos que existen dos enteros positivos
n0 y c tales que para todo n > n0 se cumple que
|f(n)| ≤ c|g(n)|
Entonces podemosescribir que
f(n) = O(g(n))
Que se lee “f(n) es del orden de g(n)”.

COMPLEJIDAD DE LOS ALGORITMOS
Rango de crecimiento; notación asintótica O

Para cualquier polinomio P(n) de grado m, P(n) = O(nm)
Ejemplo:
8n3 - 576n2 + 832n - 248 = O(n3)
También podemos escribir que
f(n) = h(n) + O(g(n)) cuando f(n) – h(n) = O(g(n))
Que recibe el nombre de notación “O mayúscula”

COMPLEJIDAD DELOS ALGORITMOS
Supongamos que dos fragmentos P1 Y P2 de un
algoritmo tienen tiempos de ejecución del orden
O(g(n)) y O(h(n)) respectivamente, entonces el
tiempo de ejecución del algoritmo es:
O(máx(g(n), h(n)))
Utilizando la notación asintótica, daremos la
complejidad de algunos algoritmos bastante
conocidos.
a) Búsqueda secuencial: O(n)
b) Búsqueda binaria: O(log n)
c) Ordenación por...