[C con Clase] [C-con-Clase]Compejidad
Steven R. Davidson
vze266ft en verizon.net
Mar Nov 28 04:49:14 CET 2006
Hola Lidia,
LiadaNet ::. wrote:
> Buenas a todos, estoy estudiendo complejidad o eficiecica en c++, la verdad
> es que no me aclaro nada con la poca información que he
> encontrado.Resumiendo que tengo examen mañana y no tengo ni idea. ALguien
> sabe algun manual, página o referencia, que realmente explique bien como se
> resuelven los problemas.Como por ejemplo de que orden seria este codigo:
> i=1;
> x =0;
> while (i<=n){
> x+=3;
> i*=2;
> }
> Se que es de O(log2n)------>Logaritmo en base dos de n
>
Veamos. El análisis de un algoritmo para determinar la complejidad
temporal se basa en la cantidad de recursos, en este caso la suma de los
periodos de tiempo de cada paso del algoritmo. Para hacernos una idea de
la solución, típicamente, queremos saber una aproximación a la cantidad
de recursos que necesitamos. En nuestro caso, queremos saber cuánto
tiempo va a tardar ejecutar un algoritmo. Una aproximación popular es la
de la "notación de omicron mayúscula" o a veces llamada "notación O
(mayúscula)".
En el ejemplo que has dado, básicamente hacemos lo siguiente:
1. i <= n
2. x += 3
3. i *= 2
4. i <= n
5. x += 3
6. i *= 2
7. i <= n
8. x += 3
9. i *= 2
.
.
.
Para tener una idea de cuánto tiempo va a tardar aproximadamente la
ejecución de este algoritmo en términos de la cantidad de valores
entrantes. Vemos que la condición se basa en el valor de 'n'. Veamos
algunos casos:
n = 1
-----
i=1
Iteraciones: 0
n = 2
-----
i=1
i=2
Iteraciones: 1
n = 3
-----
i=1
i=2
i=4
Iteraciones: 2
n = 4
-----
i=1
i=2
i=4
i=8
Iteraciones: 2
n = 5
-----
i=1
i=2
i=4
i=8
Iteraciones: 2
n = 6
-----
i=1
i=2
i=4
i=8
Iteraciones: 2
.
.
.
n = 8
-----
i=1
i=2
i=4
i=8
Iteraciones: 3
Analizando estos casos, vemos que el patrón es el siguiente:
k
2 <= n, donde 'k' es la cantidad de iteraciones y 'n' la cantidad entrante
Por lo tanto, en términos de 'n', tenemos que,
k <= lg n, donde 'lg' es el logaritmo en base 2.
Aquí tenemos que la complejidad temporal del algoritmo es O( lg n ).
Recuerda que la notación O es una aproximación de la cantidad de tiempo
que hace falta para ejecutar el algoritmo. Formalmente, la notación O
describe la aproximación del límite o cota superior.
Te pongo otro ejemplo,
suma = 0;
for( int i=0; i<n; i++ )
suma += lista[n];
Dado que 'n' es la cantidad entrante, vemos que la cota superior del
coste temporal es lineal; o sea, 0 <= i <= n-1. Por lo tanto, la
complejidad de este algoritmo es O( n ).
Otro ejemplo:
for( int i=0; i<10; i++ )
cout << info[i];
Aquí, no se ve claramente el valor de 'n', pero sí vemos que este bucle
siempre realizará 10 iteraciones. Por lo tanto, la complejidad se basa
en un tiempo constante (10 iteraciones) irrelevantemente del valor de
'n'. Esto se suele expresar de esta manera: O( 1 ) o incluso O( C ),
donde 'C' representa un valor constante cualquiera.
Espero que esto te ayude.
Steven
Más información sobre la lista de distribución Cconclase