微信客服：xiaoxionga100
微信客服：ITCS521
程序代写案例-CSC510-04
时间：2021-10-13
CSC510-04 Analysis of Algorithms Recurrence Relations Jose Ortiz jortizco@sfsu.edu Copyright Jose Ortiz Recurrence Relations Overview • Motivation and Formal Definition • The Back Substitution Method • The Master Theorem • Practice Problems 2 Recurrence Relations Motivation • Defining sequences for recurrent functions using summations is not intuitive. • Base cases cannot be represented in sequences • Input size n repeats itself or decrease for each recurrent call. 3 Recurrence Relations Formal Definition • Recurrent relation is an equation that defines itself • Also known as recurrence equations • At least one non-recursive output (base cases) • One or more recursive cases (calls itself ) • Once solved, they define the time complexity of the recurrence. 4 Recurrence Relations Techniques • Two techniques to solve recurrent relations • Back Substitution • Recurrently substitutes T(n) until there is a clear sequence that defines a pattern. • Master Theorem • Provides an elegant solution in asymptotic terms for recurrence relations 5 Solving Recurrence Relations by The Back Substitution Method Recurrence Relations Back Substitution func greetings(n) { —> T(n) if (n<=0) -> T(0)= 0 return; print(“Hello”) —> 1 greetings(n-1) —> T(n-1) } 7 Solve by Back Substitution : . . Continue for k times . Assume (n-k) = 0 (base case). Thus, n=k. Then, T(n) = T(n − 1) + 1 T(n) = [T(n − 2) + 1] + 1 T(n) = T(n − 2) + 2 T(n) = [T(n − 3) + 1] + 2 T(n) = T(n − 3) + 3 T(n) = T(n − k) + k T(n) = T(0) + n→ T(n) = 0 + n − > O(n) Recurrence Relations Back Substitution func greetings(n) { —> T(n) if (n<=0) -> T(0) = 1 return 1; print(“Hello”) —> 1 greetings(n-1) —> T(n-1) } 8 Solve by Back Substitution : . . Continue for k times . Assume (n-k) = 0 (base case). Thus, n=k. Then, T(n) = T(n − 1) + 1 T(n) = [T(n − 2) + 1] + 1 T(n) = T(n − 2) + 2 T(n) = [T(n − 3) + 1] + 2 T(n) = T(n − 3) + 3 T(n) = T(n − k) + k T(n) = T(0) + n→ T(n) = 1 + n − > O(n) Recurrence Relations Back Substitution (loops) func greetings(n) { —> T(n) if (n<1) return; for(i=0; i
}
greetings(n-1) —> T(n-1)
}
T(n) = T(n-1) + n
9
Solve by Back Substitution :
.
. Continue for k times
.
Assume (n-k) = 0 (base case). Thus,
n=k. Then,
T(n) = T(n − 1) + n
T(n) = [T(n − 2) + (n − 1)] + 1
T(n) = T(n − 2) + (n − 1) + 1
T(n) = [T(n − 3) + (n − 2)] + (n − 1) + 1
T(n) = T(n − 3) + (n − 2) + (n − 1) + 1
T(n) = T(n − k) + (n − (k − 1)) + (n − (k − 2)) + . . . + (n − 1) + n
T(n) = T(n − n) + (n − (n − 1)) + (n − (n − 2)) + . . . + (n − 1) + n
T(n) = T(1) + 1 + 2 + 3 + . . . + (n − 1) + n
T(n) = (n(n + 1)
2
) = O(n2)
Recurrence Relations Back Substitution (dividing)
func greetings(n) { —> T(n)
if (n<=1) return;
print(“Hello”) —> 1
greetings(n/2) —> T(n/2)
}
T(n) = T(n/2) + 1
10
Solve by Back Substitution :
.
. Continue for k times
.
T(n) = T(n/2) + 1
T(n) = [T(n/22) + 1] + 1
T(n) = [T(n/22) + 2
T(n) = [T(n/23) + 1] + 2
T(n) = T(n/23) + 3
T(n) = T(n/2k) + k
Assume (n/2k) = 1 (base case) then k = log n
T(n) = T(1) + log n
T(n) = 0 + log n
T(n) = Θ(logn)
Recurrence Relations Back Substitution (dividing)
func greetings(n) { —> T(n)
if (n<=1) return 1;
for(i=0; i
print(“Hello”)
}
greetings(n/2) —> T(n/2)
greetings(n/2) —> T(n/2)
}
T(n) = 2T(n/2) + n
11
Solve by Back Substitution :
.
. Continue for k times
.
T(n) = 2T(n/2) + n
T(n) = 2[2T( n
22
) + n
21
] + n
T(n) = 22T( n
22
) + 2n
T(n) = 22[2T( n
23
) + n
22
] + 2n
T(n) = 23T( n
23
) + 3n
T(n) = 2kT(n/2k) + kn
Assume T(n/2k) = T(1) (base case) then 2k = n; k = log n
T(n) = nT(1) + nlogn
T(n) = n + n log n = Θ(nlogn)
Recurrence Relations Back Substitution Example
12
Assuming that , solve the following recurrence equation
T(1) = 1 T(n) = 2T(n
2
) + n3
T(n) = 2T(n
2
) + n3
T(n) = 22T( n
22
) + n
3
22
+ n3
T(n) = 23T( n
23
) + n
3
24
+ n
3
22
+ n3
After k steps . . .
T(n) = 2kT( n
2k
) + n3( 1
40
+ 1
41
+ . . . + 1
4k−1
)
T(n) = 2kT(1) + n3(
k−1
∑
i=0
( 1
4
)i)
T(n) = n + 4n
3
3
(1 − 1
n2
)
T(n) = O(n3)
Assume:
T( n
2k
) = 1
2k = n
k = log n
Recurrence Relations Back Substitution Example
13
Assuming that , solve the following recurrence equation
T(1) = 1 T(n) = 3T( n
4
) + n
T(n) = 3T(n
4
) + n
T(n) = 32T( n
42
) + 3n
4
+ n
T(n) = 32T( n
42
) + 3
2n
42
+ 3n
4
+ n
After k steps . . .
T(n) = 3kT( n
4k
) + n( 3
4
+ 3
2
42
+ 3
3
43
+ . . . + 3
k−1
4k−1
)
T(n) = 3log4 nT(1) + n(
k−1
∑
i=1
( 3
4
)i)
T(n) = nlog4 3T(1) + 4n(1 − n
log4 3
n
)
T(n) = O(n)
Assume:
T( n
4k
) = 1
4k = n
k = log4 n
Recurrence Relations Back Substitution Example
14
Assuming that , solve the following recurrence equation
.
.
T(0) = 1
T(n) = T(n − 1) + logn
T(n) = T(n − 2) + log(n − 1) + logn
T(n) = T(n − 3) + log(n − 2) + log(n − 1) + logn
T(n) = T(n − k) + log(n − (k − 1)) + log(n − (k − 2)) + . . . + log(1)
T(n) = T(n − k) + log(n!)
T(n) = T(0) + nlogn
T(n) = 1 + nlogn
T(n) = O(nlogn)
Note that log(n!) ≈ nlogn
Assume:
n − k = 0
n = k
T(0) = 1
Recurrence Equations Exam Review
15
1.
2.
3.
4.
5.
T(n) = 7T( n
3
) + n2
T(n) = 16T( n
4
) + n2
T(n) = 7T( 9n
10
) + n
T(n) = 2T( n
2
) + n
log n
T(n) = T(n − 1) + logn
Solving Recurrence Relation
Using The Master Theorem
Recurrence Relations
The Master Theorem for conquering and dividing functions
T(n) = aT( n
b
) + f(n)); (1) logb a; (2) k
a ≥ 1; b > 1; f(n) = Θ(nk logp n)
Case 1 : if logb a > k then Θ(nlogb a)
Case 2 : if logb a = k
if p > − 1 Θ(nk logp+1 n)
if p = − 1 Θ(nk log log n)
if p < − 1 Θ(nk)
Case 3 : if logb a < k;
if p ≥ 0 Θ(nk logp n)
if p < 0 Θ(nk)
17
Example:
a = 1
b = 2
p = 0
k= 0
Case 2 because
And since p > -1 then
T(n) = T(n
2
) + 1
log2 1 = 0
Θ(n0 log0+1 n) = Θ(log n)
Recurrence Relations
The Master Theorem for conquering and dividing functions
T(n) = aT( n
b
) + f(n)); (1) logb a; (2) k
a ≥ 1; b > 1; f(n) = Θ(nk logp n)
Case 1 : if logb a > k then Θ(nlogb a)
Case 2 : if logb a = k
if p > − 1 Θ(nk logp+1 n)
if p = − 1 Θ(nk log log n)
if p < − 1 Θ(nk)
Case 3 : if logb a < k;
if p ≥ 0 Θ(nk logp n)
if p < 0 Θ(nk)
18
Example:
a = 2
b = 2
p = 0
k= 0
Case 1 because
T(n) = 2T(n
2
) + 1
log2 2 > 0
Θ(n1) = Θ(n)
Recurrence Relations
The Master Theorem for conquering and dividing functions
T(n) = aT( n
b
) + f(n)); (1) logb a; (2) k
a ≥ 1; b > 1; f(n) = Θ(nk logp n)
Case 1 : if logb a > k then Θ(nlogb a)
Case 2 : if logb a = k
if p > − 1 Θ(nk logp+1 n)
if p = − 1 Θ(nk log log n)
if p < − 1 Θ(nk)
Case 3 : if logb a < k;
if p ≥ 0 Θ(nk logp n)
if p < 0 Θ(nk)
19
Example:
a = 4
b = 2
p = 0
k=1
Case 1 because
T(n) = 4T(n
2
) + n
log2 4 > 1
Θ(nlog2 4) = Θ(n2)
Recurrence Relations
The Master Theorem for conquering and dividing functions
T(n) = aT( n
b
) + f(n)); (1) logb a; (2) k
a ≥ 1; b > 1; f(n) = Θ(nk logp n)
Case 1 : if logb a > k then Θ(nlogb a)
Case 2 : if logb a = k
if p > − 1 Θ(nk logp+1 n)
if p = − 1 Θ(nk log log n)
if p < − 1 Θ(nk)
Case 3 : if logb a < k;
if p ≥ 0 Θ(nk logp n)
if p < 0 Θ(nk)
20
Example:
a = 8
b = 2
p = 0
k=3
Case 2 because
Then, since p>-1,
T(n) = 8T(n
2
) + n3
log2 8 = 3
Θ(n3 log0+1 n) = Θ(n3 log n)
Recurrence Relations
The Master Theorem for conquering and dividing functions
T(n) = aT( n
b
) + f(n)); (1) logb a; (2) k
a ≥ 1; b > 1; f(n) = Θ(nk logp n)
Case 1 : if logb a > k then Θ(nlogb a)
Case 2 : if logb a = k
if p > − 1 Θ(nk logp+1 n)
if p = − 1 Θ(nk log log n)
if p < − 1 Θ(nk)
Case 3 : if logb a < k;
if p ≥ 0 Θ(nk logp n)
if p < 0 Θ(nk)
21
Example:
a = 7
b = 3
p = 0
k=2
Case 3 because
Then, since p = 0,
T(n) = 7T(n
3
) + n2
log3 7 < 2
Θ(n2 log0 n) = Θ(n2)
Recurrence Relations
The Master Theorem for conquering and dividing functions
T(n) = aT( n
b
) + f(n)); (1) logb a; (2) k
a ≥ 1; b > 1; f(n) = Θ(nk logp n)
Case 1 : if logb a > k then Θ(nlogb a)
Case 2 : if logb a = k
if p > − 1 Θ(nk logp+1 n)
if p = − 1 Θ(nk log log n)
if p < − 1 Θ(nk)
Case 3 : if logb a < k;
if p ≥ 0 Θ(nk logp n)
if p < 0 Θ(nk)
22
Example:
a = 2
b = 2
p = -1
k=1
Case 2 because
Then, since p=-1,
T(n) = 2T(n
2
) + n
log n
→ T(n) = 2T(n
2
) + n log−1 n
log2 2 = 1
Θ(n log log n)
Recurrence Relations
The Master Theorem for conquering and dividing functions
T(n) = aT( n
b
) + f(n)); (1) logb a; (2) k
a ≥ 1; b > 1; f(n) = Θ(nk logp n)
Case 1 : if logb a > k then Θ(nlogb a)
Case 2 : if logb a = k
if p > − 1 Θ(nk logp+1 n)
if p = − 1 Θ(nk log log n)
if p < − 1 Θ(nk)
Case 3 : if logb a < k;
if p ≥ 0 Θ(nk logp n)
if p < 0 Θ(nk)
23
Example:
a = 7
b = 4
p = 0
k=0
Case 1 because
T(n) = 7T(n
4
) + 4n + 2
log4 7 > 0
Θ(nlog4 7)
Recurrence Relations Exam Review
24
1. Assuming that , solve the following recurrence equation using
the Back Substitution method
2. Check your solution using the master theorem
T(1) = 0
T(n) = 8T(n
4
) + n2 + 1
学霸联盟
