ชุดฝึกความสัมพันธ์แบบกำเริบ

ความสัมพันธ์ที่เกิดซ้ำ เป็นสมการที่กำหนดอาร์เรย์หลายมิติแบบเรียกซ้ำ

ที่นี่เราจะแก้ปัญหาเพื่อให้คำถามตามความสัมพันธ์ที่เกิดซ้ำ

Solve the recurrence reation:T(n) = 12T(n/2) + 9n2 + 2.
T(n) = 12T(n/2) + 9n2 + 2.
Here, a = 12 and b = 2 and f(n) = 9(n)2 + 2
It is of the form f(n) = O(n^c), where c = 2

รูปแบบนี้อยู่ในเงื่อนไขทฤษฎีบทของอาจารย์

So,
logb(a) = log2(12) = 3.58
Using case 1 of the masters theorm, T(n) = θ(n3.58).

Solve the recurrence reation:T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3.
T(n) = 5T(n/2 + 23) + 5n2 + 7n - 5/3

ในการลดความซับซ้อน ในกรณีที่มีค่ามาก n,n/2>> 23 ดังนั้น 23 จึงถูกละเลย

T(n) = 5T(n/2) + 5n2 + 7n - 5/3.
Further, we can take 5n2 + 7n - 5 ≃0(n2).
So, T(n) = 5T(n/2) + O(n2)

นี้ตกอยู่ภายใต้กรณีที่ 2 ของทฤษฎีบทปรมาจารย์

So, T(n) = O(n2).

ตรวจสอบว่าสิ่งต่อไปนี้อยู่ภายใต้กรณีใดๆ ของทฤษฎีบทของปรมาจารย์หรือไม่

T(n) = 2T(n/3) + 5n

ไม่ หากต้องการใช้ทฤษฎีบทต้นแบบ ฟังก์ชันควรเป็นฟังก์ชันพหุนาม

T(n) = 2T(n/5) + tan(n)

ไม่ ฟังก์ชันตรีโกณมิติไม่อยู่ภายใต้ทฤษฎีบทมาสเตอร์

T(n) = 5T(n+1) + log(n)

ไม่ ฟังก์ชันลอการิทึมไม่อยู่ภายใต้ทฤษฎีบทมาสเตอร์

T(n) = T(n-7) + en

ไม่ ฟังก์ชันเลขชี้กำลังไม่อยู่ภายใต้ทฤษฎีบทมาสเตอร์

T(n) = 9n(n/2+1 ) + 4(n2) - 17
Yes, as solved above.