ที่นี่เราจะมาดูวิธีการใช้วิธีการทดแทนเพื่อแก้ไขความสัมพันธ์ที่เกิดซ้ำ เราจะยกตัวอย่าง 2 ตัวอย่างเพื่อทำความเข้าใจให้ดีขึ้น
สมมติว่าเราใช้เทคนิคการค้นหาแบบไบนารี ในเทคนิคนี้ เราจะตรวจสอบว่ามีองค์ประกอบอยู่ที่ส่วนท้ายหรือไม่ หากมีอยู่ตรงกลาง อัลกอริทึมจะยุติลง มิฉะนั้น เราจะนำอาร์เรย์ย่อยด้านซ้ายและขวาออกจากอาร์เรย์จริงซ้ำแล้วซ้ำอีก ดังนั้นในแต่ละขั้นตอน ขนาดของอาร์เรย์จะลดลง n / 2 สมมติว่าอัลกอริทึมการค้นหาแบบไบนารีใช้เวลา T(n) ในการดำเนินการ เงื่อนไขพื้นฐานใช้เวลา O(1) ระยะเวลา ดังนั้นสมการการเกิดซ้ำจะเป็นดังนี้ -
$$T(n)=\begin{cases}T(1) &for\:n \leq 1\\2T(\frac{n}{2})+c &for\:n> 1\end{cases }$$
แก้ - เราจะแทนที่สูตรในแต่ละขั้นตอนเพื่อให้ได้ผลลัพธ์ -
$$T(n)=T(\frac{n}{2})+c$$
โดยการแทนที่ T(N/2) เราสามารถเขียนได้
$$T(n)=(T(\frac{n}{4})+c)+c$$
$$T(n)=T(\frac{n}{4})+2c$$
$$T(n)=T(\frac{n}{8})+3c$$
$$T(n)=T(\frac{n}{2^{k}})+kc$$
ตอนนี้ถ้า $$(\frac{n}{2^{k}})$$ ถึง 1 ก็แสดงว่า 2 k คือ น. ดังนั้นค่าของ k คือ log2 𝑛
ความซับซ้อนของ T(n) =ϴ(log n)
ในทำนองเดียวกัน หากเราเลือกตัวอย่างอื่น เช่น การเรียงลำดับการผสาน ในกรณีนั้น เราจะแบ่งรายการออกเป็นสองส่วน การแบ่งส่วนนี้จะเกิดขึ้นจนกว่ารายการจะมีขนาดเพียง 1 เท่านั้น หลังจากนั้นเราจะรวมรายการตามลำดับ อัลกอริทึมการรวมจะใช้เวลา O(n) ดังนั้น หากอัลกอริธึมการเรียงลำดับการผสานใช้เวลา T(n) จากนั้นแบ่งมันออกเป็นสองส่วน และทำภารกิจเดียวกันสำหรับแต่ละรายการ พวกเขาจะใช้ T(n/2) เป็นต้น ดังนั้นความสัมพันธ์ที่เกิดซ้ำจะเป็นดังนี้ −
$$T(n)=\begin{cases}T(1) &for\:n =1\\2T(\frac{n}{2})+cn &for\:n> 1\end{cases} $$
แก้ - เราจะแทนที่สูตรในแต่ละขั้นตอนเพื่อให้ได้ผลลัพธ์ -
$$T(n)=2T(\frac{n}{2})+cn$$
โดยการแทนที่ T(N/2) เราสามารถเขียนได้
$$T(n)=2(2T(\frac{n}{4})+\frac{cn}{2}) +cn$$
$$T(n)=4T(\frac{n}{4}) +2cn$$
$$T(n)=8T(\frac{n}{8}) +3cn$$
$$T(n)=2^{k}T(\frac{n}{2^{k}}) +kcn$$
ตอนนี้ถ้า $$(\frac{n}{2^{k}})$$ ถึง 1 ก็แสดงว่า 2 k คือ น. ดังนั้นค่าของ k คือ log2 . และ T(n) จะเป็น −
𝑇(𝑛) =𝑛𝑇(1) + 𝑐𝑛 บันทึก2 𝑛
ความซับซ้อนคือ θ(n log n)
