Apa exercicios

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)=2kT(n-k)

Supondo n-k=1, temos k=n-1
T(n)=2n-1.T(1) => 2n-1.1
T(n)=2n-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
=34(n-4)+2.3³+2.3²+2.3+2^[b]

...
Após k passos, temos:
T(n)= 3kT(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) = 3n-1 + 2((3n-1 - 1/(3 - 1)*) = 3n-1 + 3n-1 - 1
T(n) = 2.3n-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