Isso, seria assim mesmo :) 2009/5/30 HugLeo <[email protected]>
> 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^n -1 > > > 2009/5/30 Rafael Ando <[email protected]> > > 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 todos os valores. Dá pra ver que tanto mostrando que f(n) -> f(n+1), ou >> que f(n-1) -> f(n), conseguimos mostrar que "quando ela vale para um certo >> valor, também vale para o próximo". >> >> O seu exemplo é meio estranho! n = 2^n -1 não é uma equação verdadeira, >> pra começar... Acho que vc quis dizer: >> >> Seja T(n) = 2^n - 1. Prove que T(n) = 2T(n-1) + 1. Não é necessário >> "indução" para provar essa. O que vc fez está correto, mas não é indução... >> vc só substituiu a equação de T(n) e mostrou que vale. >> >> Por outro lado, se tivéssemos: >> >> Seja T(0) = 0 e T(n) = 2T(n-1) + 1, n>0. Prove T(n) = 2^n -1 (n≥0). (note >> que os dois problemas são diferentes). >> >> Nesse caso poderíamos usar indução para demostrar... Verificamos que o >> caso inicial vale substituindo n=0. Em seguida, demostra-se (como acima) que >> se hipótese vale para n-1, então vale para n. Poderíamos, é claro, também >> ter provado a hipótese para n+1 a partir de n, também daria certo. >> >> 2009/5/30 HugLeo <[email protected]> >> >> 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) + 1 = 2(2^n -1) + 1 = 2^[n+1] + 1 >>> >>> Qual das duas alternativas é certa ou melhor e por que funciona? >>> >>> >>> >>> -- >>> -hUgLeO-♑ >>> >> >> >> >> -- >> Rafael >> > > > > -- > -hUgLeO-♑ > -- Rafael
