สมการการเกิดซ้ำในโครงสร้างข้อมูล

ระหว่างการวิเคราะห์อัลกอริธึม เราพบความสัมพันธ์ที่เกิดซ้ำ ความสัมพันธ์ที่เกิดซ้ำเหล่านี้โดยพื้นฐานแล้วใช้ฟังก์ชันเดียวกันในนิพจน์ ในกรณีส่วนใหญ่สำหรับการวิเคราะห์อัลกอริธึมแบบเรียกซ้ำ และการแบ่งและพิชิตอัลกอริธึม เราจะได้ความสัมพันธ์ที่เกิดซ้ำ

ที่นี่เราจะดูตัวอย่างหนึ่งของสมการการเกิดซ้ำโดยใช้ตัวอย่างบางส่วน สมมติว่าเราใช้เทคนิคการค้นหาแบบไบนารี ในเทคนิคนี้ เราจะตรวจสอบว่ามีองค์ประกอบอยู่ที่ส่วนท้ายหรือไม่ หากมีอยู่ตรงกลาง อัลกอริทึมจะยุติลง มิฉะนั้น เราจะนำอาร์เรย์ย่อยด้านซ้ายและขวาออกจากอาร์เรย์จริงซ้ำแล้วซ้ำอีก ดังนั้นในแต่ละขั้นตอน ขนาดของอาร์เรย์จะลดลง n / 2 สมมติว่าอัลกอริทึมการค้นหาแบบไบนารีใช้เวลา T(n) ในการดำเนินการ เงื่อนไขพื้นฐานใช้เวลา O(1) ระยะเวลา ดังนั้นสมการการเกิดซ้ำจะเป็นดังนี้ -

$$T(n)=\begin{cases}T(1) &for\:n \leq 1\\T(|\frac{n}{2}\rvert)+c &for\:n> 1\ จบ{cases}$$

ในทำนองเดียวกัน หากเราเลือกตัวอย่างอื่น เช่น การเรียงลำดับการผสาน ในกรณีนั้น เราจะแบ่งรายการออกเป็นสองส่วน การแบ่งส่วนนี้จะเกิดขึ้นจนกว่ารายการจะมีขนาดเพียง 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} $$

เราสามารถแก้สมการเหล่านี้ได้โดยใช้วิธีการต่างๆ เช่น การแทนที่ วิธีแผนผังการเกิดซ้ำ และความสัมพันธ์แบบพิเศษบางประเภทสามารถแก้ไขได้โดยใช้วิธีมาสเตอร์