ทฤษฎีบทขั้นสูงสำหรับการแบ่งและพิชิตการเกิดซ้ำ

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

ตัวอย่าง

มาดูตัวอย่างเพื่อเรียนรู้เพิ่มเติมเกี่ยวกับเทคนิคการแบ่งและพิชิตกัน −

function recursive(input x size n)
   if(n < k)
      Divide the input into m subproblems of size n/p.
      and call f recursively of each sub problem
   else
      Solve x and return

รวมผลลัพธ์ของปัญหาย่อยทั้งหมดและคืนวิธีแก้ปัญหาให้กับปัญหาเดิม

คำอธิบาย − ในปัญหาข้างต้น ชุดปัญหาจะถูกแบ่งออกเป็นปัญหาย่อยที่เล็กกว่าซึ่งสามารถแก้ไขได้ง่าย

ทฤษฎีบทปรมาจารย์สำหรับการแบ่งแยกและพิชิต เป็นทฤษฎีบทการวิเคราะห์ที่สามารถใช้เพื่อกำหนดค่า big-0 สำหรับอัลกอริธึมความสัมพันธ์แบบเรียกซ้ำ ใช้เพื่อค้นหาเวลาที่อัลกอริทึมต้องการและแสดงในรูปแบบสัญลักษณ์กำกับ

ตัวอย่างค่ารันไทม์ของปัญหาในตัวอย่างข้างต้น −

T(n) = f(n) + m.T(n/p)

สำหรับอัลกอริธึมแบบเรียกซ้ำส่วนใหญ่ คุณจะสามารถค้นหาความซับซ้อนของเวลาสำหรับอัลกอริธึมโดยใช้ทฤษฎีบทของมาสเตอร์ แต่มีบางกรณี ทฤษฎีบทของมาสเตอร์อาจไม่สามารถใช้ได้ เหล่านี้เป็นกรณีที่ไม่สามารถใช้ทฤษฎีบทของอาจารย์ได้ เมื่อปัญหา T(n) ไม่เป็นโมโนโทน เช่น T(n) =sin n ฟังก์ชันปัญหา f(n) ไม่ใช่พหุนาม

เนื่องจากทฤษฎีบทหลักในการค้นหาความซับซ้อนของเวลาไม่ได้มีประสิทธิภาพมากในกรณีเหล่านี้ และได้รับการออกแบบทฤษฎีบทขั้นสูงขั้นสูงสำหรับการเรียกซ้ำแบบเรียกซ้ำ มันคือการออกแบบเพื่อจัดการกับปัญหาการเกิดซ้ำของแบบฟอร์ม -

T(n) = aT(n/b) + ø((n^k)logpn)

โดยที่ n คือขนาดของปัญหา

a =จำนวนปัญหาย่อยในการเรียกซ้ำ a> 0

n/b =ขนาดของแต่ละปัญหาย่อย b> 1, k>=0 และ p เป็นจำนวนจริง

สำหรับการแก้ปัญหาประเภทนี้ เราจะใช้วิธีแก้ไขปัญหาต่อไปนี้

• ถ้า a>b_k จากนั้น T(n) =∅ (nlogba)
• ถ้า a =b_k แล้ว
  • ถ้า p> -1 แล้ว T(n) =∅(บันทึก nlogba ^p+1 น)
  • ถ้า p =-1 แล้ว T(n) =∅(nlog_ba loglogn)
  • ถ้า p <-1 แล้ว T(n) =∅(nlog_ba )
• ถ้าเป็นk แล้ว
  • ถ้า p> =0 แล้ว T(n)=∅(n_k บันทึก_p น)
  • ถ้า p<0 แล้ว T(n) =∅(nk)

เราจะคำนวณความซับซ้อนของอัลกอริธึมบางอย่างโดยใช้อัลกอริธึมหลักขั้นสูง -

การค้นหาไบนารี − t(n) =θ(logn)

การจัดเรียงแบบผสาน − T(n) =θ(nlogn)