TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Apa exercicios

Por:   •  5/5/2015  •  Trabalho acadêmico  •  781 Palavras (4 Páginas)  •  346 Visualizações

Página 1 de 4

1) O tempo levado para subir a escada é a soma dos tempos levados para subir cada degrau:


T(n) = T(n-1) + T(n-2) + T(n-3) + ...+ T(1)

T(n) = T(n-1) + T(n-2) + T(n-3) + ...+ 1

Mas se analisarmos o T(n-1) percebemos que ele é igual ao restante do somatório:
T(n-1) = T(n-2) + T(n-3) + ...+ 1


Substituindo temos que:
T(n) = T(n-1) + T(n-1)
T(n) = 2T(n-1)

Sendo assim, as equações de recorrência são:
T(1)=1
T(n)=2T(n-1)

Resolvendo a equação de recorrência, temos que:

T(n)=2T(n-1)
      = 2(
2T(n-1-1))

       = 2²T(n-2)
      = 2²(
2T(n-2-1))
      = 2³T(n-3)
[a]Após k passos, temos:
T(n)=2
kT(n-k)

Supondo n-k=1, temos k=n-1
T(n)=2
n-1.T(1) => 2n-1.1
T(n)=2
n-1  e  O(2n)

Outra forma de entender o problema é enxergar a escada como um vetor de n posições, em que cada degrau(posição) possui duas opções de valores: 1 para quando o degrau foi pisado e 0 para quando o degrau foi pulado. O último degrau (última posição do vetor) sempre será 1 pois é o destino, é obrigatório que seja o último passo.

[1 ou 0] [1 ou 0] [1 ou 0] ... [1]

Como são n-1 posições e temos 2 opções para cada, temos que todas as combinações diferentes podem ser representadas pela expressão 2n-1.

Mas dessa forma estamos fazendo o processo inverso até chegar nas equações de recorrência.  




2) 
T(1)=1
T(n)=3T(n-1)+2, para todo n>1

T(n)=3T(n-1)+2
= 3(
3T(n-1-1)+2)+2
=3²T(
n-2)+2.3+2
=3²(
3T(n-2-1)+2)+2.3+2
=3³T(
n-3)+3.3²+2.3+2
=3³(
3T(n-3-1)+2)+2.3²+2.3+2
=3
4(n-4)+2.3³+2.3²+2.3+2[b]

...
Após k passos, temos:
T(n)= 3
kT(n-k)+2.3k-1+...+2.3²+2.3¹+2.3°


Ao final do processo esperamos obter:
Em T(n-k), n-k = 1 temos k=n-1, logo:


T(n) = 3(n-1)T(1) +2.3(n-2)+...+2.3²+2.3¹+2.3°

T(n) = 3(n-1)T(1) + i=0 n-2 2.3i => 3(n-1) + 2 i=0n-2 3i

T(n) = 3
n-1 + 2((3n-1 - 1/(3 - 1)*) = 3n-1 + 3n-1 - 1
T(n) = 2.3
n-1 - 1 => O(3n)

*Obs.: Para resolver o somatório usamos a seguinte fórmula:

S = i=0 n ai = 1 + a + a2 + ... + an

Multiplicamos por (a-1) nos dois lados:

(a-1) S = 1 + a + a2 + ... + an .(a-1)

(a-1) S = a + a2 + ... + an + an+1 - 1 - a - a2 - ... - an

S = an+1 - 1 / a - 1[c]

3)

a) O pior caso é quando o vetor está na ordem inversa, pois é necessário trocar todos os elementos, em todas as iterações.

9

8

7

6

5

8

9

7

6

5

7

9

8

6

5

6

9

8

7

5

5

9

8

7

6

5

8

9

7

6

5

7

9

8

6

5

6

9

8

7

5

6

8

9

7

5

6

7

9

8

5

6

7

8

9



Sendo assim, a complexidade é dada pele somatório de n-1 até 1:

T(n) = (n - 1) + (n – 2) + ... + 2 + 1

...

Baixar como (para membros premium)  txt (4.6 Kb)   pdf (147.2 Kb)   docx (15 Kb)  
Continuar por mais 3 páginas »
Disponível apenas no TrabalhosGratuitos.com