[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