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

Published on 13/04/2010 in Análise Alg. 1218/32. 0 Comments

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 
——————————————————————————
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   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++;

0 Responses to “Análise de Algorítimos 1218/32 – Aula 5 – 12/04/2010”

Feed for this Entry Trackback Address
  • No Comments

Leave a Reply

You must login to post a comment.

Login