Solução de relações de recorrência 'Chip & Conquer'

7

Fui encarregado de resolver algumas relações de recorrência e tenho tido problemas com as chamadas relações 'chip & conquistar'.

Aqui estão alguns problemas de exemplo:

T(n)=T(n5)+cn2

e

T(n)=T(n2)+logn

Eu deveria estar dando uma resposta na notação Θ . Como faço para resolver e resolver relações como essas?

Rafael
fonte

Respostas:

4

Para simplificar, vamos assumir que divide e que para algum número inteiro .5nn/2=n5kk>0

T(n)=T(n5)+cn2T(n)=cn2+c(n5)2+c(n10)2+c(n15)2+...+c52+c02=c(n2+(n5)2+(n10)2+(n15)2+...+52+02)c(n2+(n5)2+(n10)2+(n/2)2)c(n/2)(1/5)(n/2)2)=cn3/40=(c/40)n3=Ω(n3)T(n)=cn2+c(n5)2+c(n10)2+c(n15)2+...+c52+c02c(n/5)n2cn3=O(n3)

Concluímos que .T(n)=Θ(n3)


Vamos supor, por simplicidade, que para um número inteiro .n/2=n2kk>1

T(n)=T(n2)+logn=logn+log(n2)+log(n4)+...+log(4)logn+log(n2)+log(n4)+...+log(n/2)(n/2)log(n/2)=Ω(nlogn)T(n)=T(n2)+logn=logn+log(n2)+log(n4)+...+log(4)(n/2)logn=O(nlogn)

Concluímos que .T(n)=Θ(nlogn)

Avi Cohen
fonte
0

Expanda a recorrência e resuma.

Exemplo 1:

T(n)=T(n5)+O(n2)=T(n10)+O(n2)==T(0)+{n/5 terms, each O(n2)}

Agora digamos . Isso seria geralmente dado na pergunta.T(0)=c

Então, isso somaria(n/5).O(n2)=O(n3)

Exemplo 2:

T(n)=T(n2)+logn=T(n4)+log(n2)+log(n)==T(0)+log(n2k)++log(n)=c+log(n2k)++log(n2)+log(n)=c+nlog(n)
Gilles 'SO- parar de ser mau'
fonte
Era para ser + cn ^ 2 e não = cn ^ 2. Erros de digitação parvos!