DAA - ปัญหาสูงสุด - นาที

ให้เราพิจารณาปัญหาง่ายๆที่สามารถแก้ไขได้ด้วยเทคนิคการหารและพิชิต

คำชี้แจงปัญหา

Max-Min Problem ในการวิเคราะห์อัลกอริทึมคือการค้นหาค่าสูงสุดและต่ำสุดในอาร์เรย์

วิธีการแก้

เพื่อค้นหาตัวเลขสูงสุดและต่ำสุดในอาร์เรย์ที่กำหนด numbers[] ขนาด nสามารถใช้อัลกอริทึมต่อไปนี้ได้ อันดับแรกเราเป็นตัวแทนของไฟล์naive method แล้วเราจะนำเสนอ divide and conquer approach.

วิธีไร้เดียงสา

วิธีNaïveเป็นวิธีพื้นฐานในการแก้ปัญหาใด ๆ ในวิธีนี้สามารถหาจำนวนสูงสุดและต่ำสุดแยกกันได้ ในการค้นหาตัวเลขสูงสุดและต่ำสุดสามารถใช้อัลกอริทึมที่ตรงไปตรงมาต่อไปนี้

Algorithm: Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

การวิเคราะห์

จำนวนการเปรียบเทียบในวิธีไร้เดียงสาคือ 2n - 2.

จำนวนการเปรียบเทียบสามารถลดลงได้โดยใช้วิธีหารและพิชิต ต่อไปนี้เป็นเทคนิค

วิธีการแบ่งแยกและพิชิต

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

ในปัญหาที่กำหนดนี้จำนวนองค์ประกอบในอาร์เรย์คือ $ y - x + 1 $ โดยที่ y มากกว่าหรือเท่ากับ x.

$ \ mathbf {\ mathit {Max - Min (x, y)}} $ จะส่งคืนค่าสูงสุดและต่ำสุดของอาร์เรย์ $ \ mathbf {\ mathit {numbers [x ... y]}} $

Algorithm: Max - Min(x, y) 
if y – x ≤ 1 then  
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

การวิเคราะห์

ปล่อย T(n) เป็นจำนวนการเปรียบเทียบที่ทำโดย $ \ mathbf {\ mathit {Max - Min (x, y)}} $ โดยที่จำนวนองค์ประกอบ $ n = y - x + 1 $

ถ้า T(n) แทนตัวเลขจากนั้นความสัมพันธ์การเกิดซ้ำสามารถแสดงเป็น

$$ T (n) = \ start {cases} T \ left (\ lfloor \ frac {n} {2} \ rfloor \ right) + T \ left (\ lceil \ frac {n} {2} \ rceil \ right ) +2 & for \: n> 2 \\ 1 & for \: n = 2 \\ 0 & for \: n = 1 \ end {cases} $$

ให้เราสมมติว่า n อยู่ในรูปของพลังของ 2. ดังนั้นn = 2k ที่ไหน k คือความสูงของต้นไม้เรียกซ้ำ

ดังนั้น,

$$ T (n) = 2.T (\ frac {n} {2}) + 2 = 2. \ left (\ begin {array} {c} 2.T (\ frac {n} {4}) + 2 \ end {array} \ right) + 2 ..... = \ frac {3n} {2} - 2 $$

เมื่อเทียบกับวิธีNaïveแล้วในการแบ่งแยกและพิชิตจำนวนการเปรียบเทียบจะน้อยกว่า อย่างไรก็ตามการใช้สัญกรณ์ asymptotic ทั้งสองวิธีแสดงโดยO(n).