Supongamos que se desea definir la modesta estructura de datos numero natural,
abreviada natno, donde natno = { 0, 1, 2, 3, ... }, y con dos operaciones,
la que pregunta por cero y la que adiciona.
structure NATNO
declare ZERO() ----> natno
ISZERO(natno) ----> boolean Conjunto de funciones F
SUCC(natno) ----> natno Conjunto de funciones F
ADD(natno, natno) ----> natno Conjunto de funciones F
for all x, y perteneciente a natno
let
ISZERO(ZERO) ====> true Conjunto de axiomas A
ISZERO(SUCC(x)) ====> false Conjunto de axiomas A
ADD(ZERO, y) ====> y Conjunto de axiomas A
ADD(SUCC(x), y) ====> SUCC(ADD(x, y)) Conjunto de axiomas A
end
end NATNO
Conjunto de dominios D = { natno, boolean }
Dominio designado de D = natno
Para presentar o describir un algoritmo puede usarse :
Los componentes del
lenguaje especial para la descripcion de algoritmos son :
La traducción desde este
lenguaje especial para la descripción de algoritmos a un lenguaje existente
puede ser hecha según lo que muestra la siguiente figura :
+----------------+
| |
+--->| Pre Procesador |---+
+----------------+ | | | | +----------------+ +----------------+ +----------------+
| Lenguaje |---+ +----------------+ +--->| Programa | | Compilador | | Codigo |
| | | Lenguaje |------->| Lenguaje |------->| |
| Especial |---+ +----------------+ +--->| Existente | | Existente | | Maquina |
+----------------+ | | Traducción | | +----------------+ +----------------+ +----------------+
+--->| |---+
| a Mano |
+----------------+
Nosotros utilizaremos el
lenguaje especial enunciado para la descripción de muchos ejemplos de algoritmos
del curso, y para otros tantos, utilizaremos el lenguaje existente Java.
Los bloques son conjuntos de sentencias que se ejecutan en conjunto y en
un tiempo que puede considerarse constante.
El parámetro n es el valor que caracteriza las entradas y/o salidas que
debe procesar el algorítmo. Puede observarse, que aunque deban procesarse
n elementos de entrada o salida, el tiempo de procesamiento, puede no depender
de n.
Entendemos por costo, el tiempo que requiere un bloque para ser procesado.
El costo del algoritmo, sera entonces, la sumatoria de los bloques que lo
componen, ajustado a las veces que se ejecutan.
Funcion en { 1, 2, 3, ... }, que determina el tiempo de ejecución de un algoritmo en función de n.
Funcion en { 1, 2, 3, ... }.
Si consideramos f(n) = O(g(n)) obtenemos la siguiente definición matemática
precisa de f(n). Es f(n) = O(g(n)), sí y solo sí, existen dos constantes c y n0
tal que el valor absoluto de f(n) es menor o igual que c por el valor
absoluto de g(n) para todo n >= n0.
Así |f(n)| =< c * |g(n)|, para todos los enteros positivos n, excepto un
numero finito de ellos.
Denota el órden de magnitud del tiempo de ejecución de un algoritmo.
Es una cota superior que tiene en cuenta los parametros de ejecucion de un algoritmo.
Por ejemplo, O(n), denota que el órden de magnitud del tiempo de
ejecución de un algoritmo es proporcional a n.
La notación O(g(n)) significa que el órden de magnitud del tiempo
de ejecución de un algorítmo no tarda más que una constante por g(n),
donde n es un parámetro que caracteriza las entradas y/o salidas que
debe procesar el algorítmo.
Algoritmo 1
-----------;
-----------;
-----------; Bloque A Tiempo Algoritmo 1 = A 1
-----------;
-----------; g(n) = K * 1
Algoritmo 2 g(n) = O(1) ( Constante )
-----------;
-----------; Bloque B 1
-----------;
if ( ......... )
{
-----------; Tiempo Algoritmo 2 = B + C + E
-----------; Bloque C 1
-----------; g(n) = K * 1
}
else g(n) = O(1) ( Constante )
{
-----------; Tiempo Algoritmo 2 = B + D + E
-----------; Bloque D 1
-----------; g(n) = K * 1
}
-----------; g(n) = O(1) ( Constante )
-----------; Bloque E 1
-----------;
Un ejemplo es el acceso a un elemento de un arreglo de n elementos.
Algoritmo 1
-----------;
-----------; Bloque A 1
-----------;
while ( ........ )
{
-----------;
-----------; Bloque B Tiempo Algoritmo 1 = A + B * n + C 100
-----------;
} = R + S * n =< R * n + S * n = K * n
-----------;
-----------; Bloque C g(n) = O(n) ( Lineal ) 1
-----------;
Un ejemplo es la recuperación de todos los elementos de un arreglo de n elementos.
Algoritmo 1
-----------;
-----------; Bloque A 1
-----------;
while ( ........ )
{
-----------;
-----------; Bloque B 100
-----------;
while ( ........ )
{
-----------;
-----------; Bloque C Tiempo Algoritmo 1 = A + ( B + C * n + D ) * n + E 10000
-----------;
} = A + B * n + C * n**2 + D * n + E
-----------;
-----------; Bloque D = R + S * n + T * n**2 =< R * n**2 + S * n**2 + T * n**2 = K * n**2 100
-----------;
} g(n) = O(n**2) ( Cuadratico )
-----------;
-----------; Bloque E 1
-----------;
Algoritmo 1
-----------;
-----------; Bloque A 1
-----------;
while ( ........ )
{
-----------;
-----------; Bloque B 100
-----------;
while ( ........ )
{
-----------;
-----------; Bloque C 10000
-----------;
while ( ........ )
{
-----------;
-----------; Bloque D Tiempo Algoritmo 1 = A + ( B + ( C + D * n + E ) * n + F ) * n + G 1000000
-----------;
} = A + ( B + C * n + D * n**2 + E * n + F ) * n + G
-----------;
-----------; Bloque E = A + B * n + C * n**2 + D * n**3 + E * n**2 + F * n + G 10000
-----------;
} = R + S * n + T * n**2 + U * n**3
-----------;
-----------; Bloque F =< R * n**3 + S * n**3 + T * n**3 + U * n**3 = K * n**3 100
-----------;
} g(n) = O(n**3) ( Cubico )
-----------;
-----------; Bloque G 1
-----------;
Algoritmo 1
-----------;
-----------; Bloque A 1
-----------;
while ( ........ )
{
-----------;
-----------; Bloque B Tiempo Algoritmo 1 = A + B * 2**n + C 2**100
-----------;
} = R + S * 2**n =< R * 2**n + S * 2**n = K * 2**n
-----------;
-----------; Bloque C g(n) = O(2**n) ( Exponencial ) 1
-----------;
Algoritmo 1
-----------;
-----------; Bloque A 1
-----------;
while ( ........ )
{
-----------;
-----------; Bloque B Tiempo Algoritmo 1 = A + B * log n + C log2 100
-----------;
} = R + S * log2 n =< R * log2 n + S * log2 n = K * log 2 n
-----------;
-----------; Bloque C g(n) = O(log2 n) ( Logaritmico ) 1
-----------;
Algoritmo 1
-----------;
-----------; Bloque A 1
-----------;
while ( ........ )
{
-----------;
-----------; Bloque B 100
-----------;
while ( ........ )
{
-----------;
-----------; Bloque C Tiempo Algoritmo 1 = A + ( B + C * log2 n + D ) * n + E 100 * log2 100
-----------;
} = A + B * n + C * n * log2 n + D * n + E
-----------;
-----------; Bloque D = R + S * n + T * n * log2 n 100
-----------;
} =< R * n * log2 n + S * n * log2 n + T * n * log2 n = K * n * log2 n
-----------;
-----------; Bloque E g(n) = O(n * log2 n ) ( Compuesto ) 1
-----------;
*-----------------------------------------------------------------------------*
| log2 n | n | n log2 n | n**2 | n**3 | 2**n |
|------------+------------+------------+------------+------------+------------|
| 0 | 1 | 0 | 1 | 1 | 2 |
| 1 | 2 | 2 | 4 | 8 | 4 |
| 2 | 4 | 8 | 16 | 64 | 16 |
| 3 | 8 | 24 | 64 | 512 | 256 |
| 4 | 16 | 64 | 256 | 4096 | 65536 |
| 5 | 32 | 160 | 1024 | 32768 | 2147483648 |
*-----------------------------------------------------------------------------*
Para grandes archivos de datos, algoritmos más complejos que n * log2 n,
son a menudo imprácticos.
Al analizar dos algoritmos que realizan la misma tarea normalmente
se toma como superior el que tenga una O(g(n)) mejor para valores altos de n.
Supongamos dos algoritmos, que cumplen con la misma tarea, con las
siguiente funciones :
*--------------------------------------*
| n | 10 * n | n**2 |
|------------+------------+------------|
| 1 | 10 | 0,5 |
| 5 | 50 | 12,5 |
| 10 | 100 | 50 |
| 15 | 150 | 112,5 |
| 20 | 200 | 200 |
| 25 | 250 | 312,5 |
| 30 | 300 | 400 |
*--------------------------------------*
Para n < 20 el algoritmo 1 es mejor que el algoritmo 2.
Para n = 20 el algoritmo 1 es igual que el algoritmo 2.
Para n > 20 el algoritmo 2 es mejor que el algoritmo 1.
Para valores de n chicos, las constantes deben determinarse precisamente,
ya que dependen del lenguaje y la máquina en que corren, entre muchas
otras variables.
Quizas, en este caso, hasta haya que medir en la práctica el comportamiento
de los algoritmos.
450 * * /
| /
| /
| /
| /
400 * *
| /
| /
| /
| /
350 * *
| /
| /
| * /
| /
300 * *
| /
| /
| /
| /
250 * *
| /
| /
| /
| /
200 * *
| /
| /
| /
| /
150 * *
| /
| /
| / *
| /
100 * *
| /
| /
| /
| /
50 * * *
| /
| /
| / *
|/
-----|----*----*----*----*----*----*----*-------------------------------> n
5 10 15 20 25 30 35
<------------------><------------------ .....
Algortimo 1 Algortimo 2
Un algoritmo debe ser analizado en función de :
El segundo punto es el tema de este curso de Estructuras de Datos.
En todos los casos comprometeremos tiempo por espacio o espacio por tiempo.