Algoritmia, Estructuras de Datos

...

Ejemplo 2:

sea f(n) = 3n+ 1

¿podemos decir que O(f(n) ) = g(n) = n ? si tenemos c = 4 y n 0 = 1

= > se cumple que

f(n) = 1

= > 3n+ 1 = > 3n+ 1 = > 1

para todo n > = 1

En nuestros análisis no podremos hacer una hipótesis y comprobarla, como en los ejemplo anteriores, sino que dada la función f(n), deberemos deducir g(n). Ésto podremos hacerlo usando las siguientes propiedades de la función O(n), cuya deducción está fuera del alcance del curso:

Propiedades de O(n)

- las constantes no importan: O( c * f(n) ) = c * O( f(n) ) = O( f(n) )

- Regla de la suma:

- O( f(n) + t(n) ) = max ( O( f(n) ), O( t(n) ) )

- O(f(n)) + O(t(n)) = O (f(n) + t(n))

- regla de la multiplicación: O(f(n)) * O(t(n)) = O (f(n) * t(n))

- anidación: O ( O(f(n)) ) = O (f(n))

De los ejemplos anteriores podemos deducir O(n), aplicando estas propiedades así:

O(3n3 + 2 n2 )

Regla de la suma: O( 3n 3 + 2 n 2 ) = max ( O( 3n 3 ) , O( 2 n 2 ) ) = O( 3n 3 )

Regla de las constantes: O( 3n 3 ) = O(n 3 ) = n 3

O(3n+1)

Regla de la suma: O( 3n+ 1 ) = max ( O( 3n ) , O( 1 ) ) = O( 3n)

Regla de las constantes: O( 3n) = O(n) = n

En general, lo resultados de O(n) se pueden clasificar en los siguiente órdenes (del mejor al peor):

- constante: O(f(n)) = c, donde c es una constante

- lineal: O(f(n)) = n

- logarítmica: O(f(n)) = logc(n)

- progresiva, geométrica o polinomial: O(f(n)) = nc , c>=2. Incluye cuadrático (n2) y cúbico (n3)

- Exponencial: O(f(n)) = cn, para c > 1

Los dos últimos órdenes son especialmente deficientes, y en cualquier lado que los encontremos, debemos esforzarnos en mejorar el rendimiento.

Para determinar la eficiencia de un algoritmo debemos realizar los siguientes pasos:

- Determinar una función del tiempo de ejecución del algoritmo para n datos: T (algorimo(n) ) = T(n)

- Aplicar las propiedades de O(n) para deducir O(T(n))

Dado el software es matemática, tal como demostró Allan Turing, entonces todo algoritmo tiene una expresión matemática y viceversa, es posible hacer una expresión matemática, T(n), de cualquier algoritmo .

Para ésto utilizaremos los principios del teorema de la programación estructurada, la cual establece que todo algoritmo puede ser realizado utilizando sólo las siguientes instrucciones básicas:

- Asignaciones y expresiones simples

- Secuencia

- Condición

- Ciclos

Si podemos establer una función de tiempo para cada una de estas sentencias, entonces podremos deducir dicha función para el algoritmo completo.

Recordar que usamos medidas de tiempo teóricas (adimensionales) = t = tiempo de la instrucción más simple o rápida de ejecutar en el procesador

Asignaciones y expresiones simples

T(asignación) = T(expresión simple) = t

=> O(asignación) = 1 ( orden constante )

Ésto incluye sentencias como

x = y ;

y = 5 + y * z ;

Secuencia de instrucciones

T(secuencia) = T (sentencia1) + T (sentencia2) +...+ T(sentencia n)

=> O(secuencia) = O(T (sentencia1) + T (sentencia2) +...+ T(sentencia n) )

= Max(O(T (sentencia1)), O(T (sentencia2)) +...+ O(T(sentencia n)) )

Instrucciones condicionales

IF ( condicion ) {

sentencia-then

}else{

sentencia-else

}

T(IF) = T ( condicion ) + max ( T ( sentencia-then ), T (sentencia-else) )

=> O (if) = O( T ( condicion ) + max ( T ( sentencia-then ), T (sentencia-else) ))

= max ( O(T ( condicion )), O( T ( sentencia-then )), O(T (sentencia-else) ) )

Instrucciones de iteración (for - while)

for

for (asignacion-inicial ; condicion ; asignacion-final)

sentencia-ciclo

}

T( for ) = T ( asignacion-inicial ) + ( T ( condicion ) + T ( sentencia-ciclo ) + T ( asignacion-final ) ) * v

donde v es el número máximo de veces que se repite el ciclo

while

i = 0 ; // asignacion inicial

while ( condicion ) {

sentencia-ciclo

}

T( while ) = T ( asignacion inicial ) + ( T ( condicion ) + T ( sentencia-ciclo ) ) * v

donde v es el número máximo de veces que se repite el ciclo

O(ciclo) = O ( T ( asignacion inicial ) + ( T ( condicion ) + T ( sentencia-ciclo ) ) * v )

= max (O ( T ( asignacion inicial )) + O ( (