infouem3: Análise de Algorítimos 1218/32 - Aula 5 - 12/04/2010

segunda-feira, 12 de abril de 2010

Análise de Algorítimos 1218/32 - Aula 5 - 12/04/2010

Notas de Aula (Google Docs)

Exercícios: Indução

1. Demonstrar por inducao matematica que

$\sum_{i=1}^{n}{\frac{1}{1i} < 1}$ , para $r\succeq 1$

2. Demonstrar por inducao matematica que

$n! \succ x^{n-1}$ , para n>=2

n>=2

------------------------------------------------------------------------------

Análise de fragmentos de código

A

sum = =

for (i=1; i<=m; i++) |

for(j=1l j<=n; j++) | $\Theta (n)$ | $\Theta (n^2)$

sum++; | $\Theta (1)$ | |

Analise: Como operação SUM ++ é o(1), então a complexidade do codigo é equivalente ao numero de vezes que a operação SUM ++ é O(n2)

Ou ainda: Temos dois lacos aninhados que executam r repetições cada um, com o corpo do laco interno com complexidade o(1). Assim, a complexidade total é n.nO(1)=O(n2)

B

SUM = 0;

for (i=1; c<=n; i++)

for (j=1; i<=i; j++)

sum++;

i 1 2 3 n

1..1 1..2 1..3 1..n

1 + 2 + 3 + n

A linha 1 isoladamente tem complexidade $\Theta (1)$

A linha 4 isoladamente tem complexidade $\Theta (1)$

A Quantidade de vezes que a linha 4 é executada depende da quantidade de vezes que o laço

da linha 3-4 é executada. Para tal laço, seu conteudo é executado j vezesm conj=1..i

O laço das linhas 3-4 é dependente do laço das linhas 2-4 que é executado n vezes c/ assumindo os valores de 1..n

Logo a quantidade de vezes que a linha 4 é executada é dada por:

T(n) = $\sum_{i=1}^{n}{}$

T(n) = $\frac{ n(n-1)}{2}$

T(n) = $\frac{ n^{2} }{2} + \frac{ n }{2}$

Logo a complexidade é proposrcional a $n^{2}$ , assim

T(n) = $\Theta n^{2}$

Demonstração pela definição assintótica:

$T(n) =\frac{1}{2}\cdot n^{2} + \frac{1}{2}\cdot n$ ; $T(n) = \Theta (n^2)$ ?

$\lim_{n \rightarrow \infty}{\frac{\frac{1}{2} \cdot n^{2}+ \frac{1}{2}\cdot n}{n^2} }$

$\lim_{n \rightarrow \infty}{(\frac{1}{2} \cdot n^{2}+ \frac{1}{2}\cdot n) \cdot \frac{1}{n^2} }$

$\lim_{n \rightarrow \infty }{\frac{1}{2} + \frac{1}{2^n} }$

$L=\frac{1}{2}$

Que é uma constante diferente de O logo,

$T(n) = \Theta (n^2)$

C

$T(n) = \Theta (n^2)$

sum=0 $\Theta (1)$ Considerando que n seja uma potencia de 2

for (k=1; k<=n; k*=2

for(j=1; j<=n; j++) | $\Theta (n)$

sum ++; | $\Theta (1)$ |

A linha 4 isoladamente é $\Theta (1)$

pelo laço das linhas 3-4 a linha 4 é executada N vezes. com as linhas 3-4 são n O(1) = O(n)

As linhas 3-4 são executadas uma quantidade de vezes depende do laço das linhas 2-4 onde tem-se

Iteração 1 2 3 4 .... n

K 1 2 4 8 ..... n

2p0 2p1 2p2 2p3 ......

Assim p/ saber quantas vezes seu conteudo é executado e necessario saber quantos valores diferente k assume até n(inclusive)

Supondo um índice i p/cada iteracao, dado pelo valor do expoente k em base 2, da forma

i = T +1

Para saber o valor de r na última iteracao, tem-se

$2^{r} = n$ logo lg 2^r = lg n

lg 2^r = lg n

logo

r lg2 = lg n +1 = lg n

r = lg n

E p/ saber o valor de i na última iteração tem-se

i = lg n +1

Assim, o trecho 2-4 é executado

lgn +1

$\Theta (n)m$ resultando em $T(n) = \Theta (n lg n)$

D

sum = 0;

for (k=1; k<=n; k*=2);

for (j=1; j<=k; j++);

sum++;

Nenhum comentário:

Postar um comentário

Assinar: Postar comentários (Atom)