planets-top
Published on

Divide and Conquer

Authors

Chia để trị (Divide and Conquer) là một kỹ thuật thiết kế thuật toán, trong đó bài toán lớn được chia thành các bài toán nhỏ hơn, giải quyết các bài toán nhỏ này, sau đó kết hợp kết quả để giải quyết bài toán ban đầu.

Cấu trúc của thuật toán chia để trị

Thuật toán chia để trị thường được xây dựng qua 3 bước:

  1. Chia (Divide): Chia bài toán lớn thành nhiều bài toán con nhỏ hơn, thường là các bài toán có cấu trúc tương tự bài toán ban đầu.
  2. Trị (Conquer): Giải quyết từng bài toán con. Nếu bài toán con đủ nhỏ, giải trực tiếp (base case); nếu không, tiếp tục chia nhỏ hơn nữa.
  3. Kết hợp (Combine): Kết hợp kết quả từ các bài toán con để có kết quả của bài toán ban đầu.

divide-and-conquer

Ví dụ minh họa thuật toán chia để trị

Merge Sort (Sắp xếp trộn) là một ví dụ kinh điển của thuật toán chia để trị. Nó chia mảng thành các mảng nhỏ hơn, sắp xếp từng mảng con, sau đó trộn (merge) các mảng con đã sắp xếp để tạo thành mảng đã sắp xếp hoàn chỉnh.

def merge_sort(arr):
    if len(arr) <= 1:  # Base Case: Mảng có 1 phần tử hoặc rỗng thì đã được sắp xếp
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])  # Đệ quy sắp xếp nửa bên trái
    right_half = merge_sort(arr[mid:])  # Đệ quy sắp xếp nửa bên phải

    # Kết hợp hai nửa đã sắp xếp
    return merge(left_half, left_right)

def merge(left, right):
    result = []
    i = j = 0

    # So sánh từng phần tử và trộn hai mảng
    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
    # Thêm các phần tử còn lại vào kết quả
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Giải thích:

  • Chia (Divide): Mảng được chia thành hai nửa cho đến khi mỗi mảng con chỉ có một phần tử.
  • Trị (Conquer): Sắp xếp từng mảng con (vì mảng một phần tử luôn được xem là đã sắp xếp).
  • Kết hợp (Combine): Trộn hai mảng con đã sắp xếp lại với nhau để tạo thành mảng đã sắp xếp hoàn chỉnh.

Quick Sort là một thuật toán chia để trị khác. Thuật toán này chọn một phần tử gọi là pivot, sau đó chia mảng thành hai phần: các phần tử nhỏ hơn pivot và lớn hơn pivot. Tiếp tục sắp xếp hai phần này đệ quy.

def quick_sort(arr):
    if len(arr) <= 1:  # Base Case: Mảng có 1 phần tử hoặc rỗng
        return arr

    pivot = arr[len(arr) // 2]  # Chọn pivot (ở đây chọn phần tử giữa)
    left = [x for x in arr if x < pivot]  # Các phần tử nhỏ hơn pivot
    middle = [x for x in arr if x == pivot]  # Các phần tử bằng pivot
    right = [x for x in arr if x > pivot]  # Các phần tử lớn hơn pivot

    # Đệ quy sắp xếp các phần bên trái và bên phải
    return quick_sort(left) + middle + quick_sort(right)

Giải thích:

  • Chia (Divide): Chọn pivot và chia mảng thành hai phần (nhỏ hơn và lớn hơn pivot).
  • Trị (Conquer): Sắp xếp hai phần này bằng cách gọi đệ quy quick_sort.
  • Kết hợp (Combine): Nối kết quả của phần bên trái, pivot, và phần bên phải lại với nhau.

Ưu điểm và nhược điểm của chia để trị

  • Ưu điểm:
    • Giải quyết các bài toán phức tạp một cách hiệu quả.
    • Tận dụng khả năng xử lý song song.
    • Một số thuật toán như Merge Sort, Quick Sort có độ phức tạp tốt.
  • Nhược điểm:
    • Tiêu tốn nhiều bộ nhớ do sử dụng đệ quy (stack call).
    • Nếu không chia nhỏ đúng cách hoặc không có điểm dừng, có thể dẫn đến lỗi stack overflow.

Bài toán khác sử dụng chia để trị

  • Exponentiation (Lũy thừa nhanh)
  • Tìm phần tử lớn thứ k trong mảng (Median of Medians)
  • Tìm kiếm trong ma trận 2D
Discuss on Twitter