Algorithms & Applications
Trang chủ / Module 6
🔀 Module 6 / 14 · 1 tuần

Đệ quy & Chia để trị (Divide and Conquer)

Tư duy đệ quy, phân tích độ phức tạp bằng Master Theorem, và 2 thuật toán sắp xếp kinh điển: Merge Sort và Quick Sort.

RecursionMerge SortQuick Sort
📌 Vì sao module này quan trọng

Chia để trị là một trong những mẫu tư duy thuật toán mạnh nhất — chia bài toán lớn thành các bài toán con nhỏ hơn cùng dạng, giải từng phần rồi hợp nhất. Merge Sort và Quick Sort không chỉ là thuật toán sắp xếp kinh điển mà còn là ví dụ mẫu mực để hiểu tư duy này trước khi áp dụng cho các bài toán phức tạp hơn.

🎯 Mục tiêu học tập

  • Viết đúng hàm đệ quy với base case và recursive case rõ ràng, tránh đệ quy vô hạn
  • Áp dụng tư duy Chia để trị: Divide - Conquer - Combine
  • Triển khai Merge Sort và Quick Sort, so sánh đánh đổi giữa 2 thuật toán
  • Sử dụng Master Theorem (khái niệm) để phân tích nhanh độ phức tạp của thuật toán đệ quy chia để trị

Tư duy Đệ quy — Base Case & Recursive Case

def giai_thua(n: int) -> int:
    if n <= 1:                  # base case — điều kiện dừng, BẮT BUỘC phải có
        return 1
    return n * giai_thua(n - 1)  # recursive case — gọi lại chính nó với bài toán nhỏ hơn

Mọi hàm đệ quy đúng cần 2 thành phần: base case (điều kiện dừng, ngăn đệ quy vô hạn — thiếu phần này gây Stack Overflow, liên hệ trực tiếp Call Stack đã học ở Module 2) và recursive case (gọi lại chính hàm đó với 1 bài toán nhỏ hơn, tiến dần về base case). Nguyên tắc kiểm tra đệ quy đúng: giả định hàm đã hoạt động đúng cho bài toán nhỏ hơn (induction), chỉ cần kiểm tra bước hiện tại kết hợp kết quả đó đúng hay không — không cần "theo dõi" toàn bộ chuỗi gọi trong đầu.

Chia để trị: Divide - Conquer - Combine

  1. Divide: chia bài toán thành các bài toán con nhỏ hơn, cùng dạng với bài toán gốc
  2. Conquer: giải từng bài toán con (thường bằng đệ quy, cho đến khi đủ nhỏ để giải trực tiếp)
  3. Combine: hợp nhất kết quả các bài toán con thành kết quả cho bài toán gốc

Merge Sort — ổn định, độ phức tạp đảm bảo

def merge_sort(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])     # Divide + Conquer (đệ quy)
    right = merge_sort(arr[mid:])
    return merge(left, right)         # Combine

def merge(left: list, right: list) -> list:
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

Merge Sort luôn đảm bảo O(n log n) ở mọi trường hợp (best/average/worst case) — "chia đôi" luôn cân bằng, không phụ thuộc dữ liệu đầu vào. Đánh đổi: cần O(n) bộ nhớ phụ cho mảng tạm khi merge, và là thuật toán ổn định (stable — giữ nguyên thứ tự tương đối của các phần tử bằng nhau, quan trọng khi sắp xếp theo nhiều tiêu chí liên tiếp).

Quick Sort — nhanh trung bình, cần chọn Pivot khéo léo

def quick_sort(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Quick Sort chọn 1 phần tử làm pivot, chia mảng thành "nhỏ hơn pivot" và "lớn hơn pivot" (Divide), đệ quy sắp xếp từng phần (Conquer), rồi ghép lại (Combine — đơn giản hơn Merge Sort vì không cần "trộn" có thứ tự). Trung bình đạt O(n log n) và không cần bộ nhớ phụ đáng kể (sort tại chỗ trong triển khai chuẩn) — thường nhanh hơn Merge Sort trong thực tế nhờ locality bộ nhớ tốt hơn (liên hệ Module 2). Nhược điểm: trường hợp xấu nhất (pivot luôn là phần tử nhỏ nhất/lớn nhất, ví dụ dữ liệu đã sắp xếp sẵn và chọn pivot ngây thơ) suy biến thành O(n²) — các triển khai thực tế dùng chiến lược chọn pivot ngẫu nhiên hoặc "median-of-three" để giảm rủi ro này.

Merge SortQuick Sort
Worst caseO(n log n) — đảm bảoO(n²) — hiếm khi xảy ra với pivot tốt
Bộ nhớ phụO(n)O(log n) (đệ quy stack)
Ổn định (stable)CóKhông (trong triển khai chuẩn)
Thực tế thường dùng khiCần đảm bảo worst case, cần stable sort, sort external (dữ liệu không vừa RAM)Sort trong bộ nhớ thông thường, ưu tiên tốc độ trung bình

🏋️ Bài tập thực hành

Triển khai & So sánh Merge Sort vs Quick Sort

Triển khai cả Merge Sort và Quick Sort từ đầu. Đo thời gian chạy trên 3 loại dữ liệu: ngẫu nhiên, đã sắp xếp sẵn, và đảo ngược hoàn toàn (worst case cho Quick Sort với pivot ngây thơ). Ghi lại và giải thích sự khác biệt quan sát được, đặc biệt chú ý trường hợp Quick Sort suy biến.

📚 Tài nguyên học tập

✅ Tự đánh giá hoàn thành

  • Viết đúng hàm đệ quy với base case rõ ràng, không gây stack overflow
  • Áp dụng đúng mẫu Divide-Conquer-Combine cho 1 bài toán mới
  • Triển khai đúng cả Merge Sort và Quick Sort
  • Giải thích được đánh đổi giữa 2 thuật toán và khi nào chọn cái nào