Lösen von Wiederholungsbeziehungen 'Chip & Conquer'

7

Ich wurde beauftragt, einige Wiederholungsrelationen zu lösen, und ich hatte Probleme mit sogenannten "Chip & Conquer" -Relationen.

Hier sind einige Beispielprobleme:

T(n)=T(n5)+cn2

und

T(n)=T(n2)+logn

Ich soll eine Antwort geben ΘNotation. Wie gehe ich herum und löse solche Beziehungen?

Raphael
quelle

Antworten:

4

Nehmen wir der Einfachheit halber an 5 teilt n und das n/.2=n- -5k für eine ganze Zahl k>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)

Wir schließen daraus T(n)=Θ(n3).


Let's assume for simplicity that n/2=n2k for an integer k>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)

We conclude that T(n)=Θ(nlogn).

Avi Cohen
quelle
0

Expand the recurrence and sum it up.

Example 1:

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

Now let's say T(0)=c. This would be generally given in the question.

so this would sum to (n/5).O(n2)=O(n3)

Example 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- stop being evil'
quelle
It was supposed to be +cn^2 not =cn^2. Silly typos!