Recurrence Relations คืออะไร?
Recurrence Relations (ความสัมพันธ์แบบเวียนเกิด) คือสมการที่กำหนดลำดับของตัวเลขแบบเวียนเกิด โดยแต่ละพจน์ถูกนิยามจากพจน์ก่อนหน้า ใช้อย่างกว้างขวางในการวิเคราะห์ Complexity ของอัลกอริทึมแบบ Divide-and-Conquer
โจทย์ฝึกหัดและวิธีแก้
โจทย์ 1: T(n) = 12T(n/2) + 9n² + 2
T(n) = 12T(n/2) + 9n² + 2 a = 12, b = 2, f(n) = 9n² + 2 = O(n²) → c = 2 log_b(a) = log₂(12) ≈ 3.585
เนื่องจาก c < log_b(a) (2 < 3.585) ตรงเงื่อนไข Case 1 ของ Master Theorem
T(n) = Θ(n^{log₂12}) = Θ(n^{3.585})
โจทย์ 2: T(n) = 5T(n/2 + 23) + 5n² + 7n - 5/3
สำหรับค่า n ใหญ่: n/2 ≫ 23 → ทิ้ง 23 ได้ T(n) ≈ 5T(n/2) + 5n² + 7n - 5/3 5n² + 7n - 5/3 = O(n²) T(n) = 5T(n/2) + O(n²)
a = 5, b = 2, f(n) = O(n²) → c = 2
log_b(a) = log₂(5) ≈ 2.32
เนื่องจาก c > log_b(a) (2 > 2.32? ไม่ถูกต้อง - ต้องตรวจสอบอีกครั้ง)
แก้ไข: log₂(5) ≈ 2.32, c = 2 → c < log_b(a) → Case 1 ไม่ใช่ Case 2
T(n) = Θ(n^{log₂5}) = Θ(n^{2.32})
ตรวจสอบเงื่อนไข Master Theorem
Master Theorem ใช้ได้ก็ต่อเมื่อ f(n) เป็น Polynomial Function เท่านั้น
| Recurrence | ตรงเงื่อนไข? | เหตุผล |
|---|---|---|
| T(n) = 2T(n/3) + 5ⁿ | ❌ ไม่ตรง | f(n) = 5ⁿ เป็น Exponential Function |
| T(n) = 2T(n/5) + tan(n) | ❌ ไม่ตรง | f(n) = tan(n) เป็น Trigonometric Function |
| T(n) = 5T(n+1) + log(n) | ❌ ไม่ตรง | f(n) = log(n) เป็น Logarithmic Function และรูปแบบ n+1 ไม่ใช่ n/b |
| T(n) = T(n-7) + eⁿ | ❌ ไม่ตรง | f(n) = eⁿ เป็น Exponential Function และรูปแบบ n-7 ไม่ใช่ n/b |
| T(n) = 9n(n/2+1) + 4n² - 17 | ✅ ตรง | เป็น Polynomial Function สามารถลดรูปได้ |
สรุป
Master Theorem เป็นเครื่องมือที่ทรงพลังแต่มีข้อจำกัด ต้องตรวจสอบรูปแบบ f(n) และรูปแบบของ Recurrence ให้ถูกต้องก่อนนำไปใช้
