Isso, seria assim mesmo :)
2009/5/30 HugLeo
> Sim, eu escrevi errado, o certo é como você disse: T(n) = 2^n - 1
>
> Muito obrigado pela explicação, agora deu para entender ;-)
>
> Só mais um detalhe:
> Você disse "..Em seguida, demostra-se (como acima) que se hipótese vale
> para n-1, então vale
Sim, eu escrevi errado, o certo é como você disse: T(n) = 2^n - 1
Muito obrigado pela explicação, agora deu para entender ;-)
Só mais um detalhe:
Você disse "..Em seguida, demostra-se (como acima) que se hipótese vale para
n-1, então vale para n..."
Seria assim né?:
T(n)=2(2^[n-1] - 1) + 1
T(n)=2
As duas alternativas são iguais, não tem uma "melhor" que a outra.
Para entender porque funciona, vc entende pq a indução funciona? Se uma
afirmação vale para o valor inicial, e vc consegue provar que, quando ela
vale para um certo valor, também vale para o próximo, então a afirmação vale
para tod
Eu posso substituir n na minha fórmula de reccorrência para provar para n+1,
mas se eu substituir para n-1 para provar n também funciona.
Alguém saberia explicar?
O exemplo está abaixo:
n = 2^n -1
T(n) = 2T(n) + 1
Para n
T(n) = 2T(n-1) + 1 = 2(2^[n-1] - 1) + 1 = 2^n -1
Para n+1
T(n+1) = 2T(n
4 matches
Mail list logo
