Algoritmia, Estructuras de Datos
Enviado por monto2435 • 11 de Diciembre de 2018 • 2.332 Palabras (10 Páginas) • 346 Visitas
...
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 ( (
...