หลักการแบบ divide-and-conquer คืออะไร?

Question

Accepted Answer

**Divide and conquer** แก้ปัญหาด้วยการ (1) **แบ่ง (dividing)** ปัญหาออกเป็นปัญหาย่อยที่เล็กลง (2) **จัดการ (conquering)** แต่ละปัญหาย่อยแบบ recursive และ (3) **รวม (combining)** ผลลัพธ์เข้าด้วยกัน อัลกอริทึมที่มีประสิทธิภาพจำนวนมากใช้รูปแบบนี้

## แนวคิด

หากปัญหาย่อยเป็นอิสระต่อกันและหดเล็กลงอย่างรวดเร็ว ปริมาณงานทั้งหมดจะเป็นไปตาม recurrence ที่คุณสามารถวิเคราะห์ได้ด้วย **Master Theorem**

## ตัวอย่าง: หาค่ามากที่สุดด้วย divide and conquer

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: one element
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # conquer left
    right = max_dc(arr, mid + 1, hi)   # conquer right
    return max(left, right)            # combine

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## ตัวอย่างคลาสสิก

- **Merge sort / quicksort** — การ sort แบบ O(n log n)
- **Binary search** — O(log n)
- **Fast exponentiation, Karatsuba multiplication, closest pair**

## ความซับซ้อน

โดยทั่วไป T(n) = a·T(n/b) + f(n); สำหรับ merge sort นั้น T(n) = 2T(n/2) + O(n) = **O(n log n)**

## เมื่อไรควรใช้ / ข้อควรระวัง

ใช้เมื่อปัญหา **แบ่งได้อย่างชัดเจน** ออกเป็นปัญหาย่อยที่เป็นอิสระต่อกัน หากปัญหาย่อย **ทับซ้อนกัน** ควรเลือกใช้ dynamic programming แทน (เพื่อหลีกเลี่ยงการคำนวณซ้ำ) overhead จาก recursion และขั้นตอนการ combine อาจกลายเป็นต้นทุนหลักเมื่อ input มีขนาดเล็ก

## ทำไมจึงสำคัญ

Divide and conquer เป็นแม่แบบที่นำกลับมาใช้ซ้ำได้ ซึ่งอยู่เบื้องหลังอัลกอริทึมที่มีประสิทธิภาพเป็นสัดส่วนมหาศาล

การรู้จักจดจำรูปแบบนี้ช่วยให้คุณสร้างและวิเคราะห์อัลกอริทึมใหม่ได้อย่างรวดเร็วด้วย recurrences

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