Thuật toán chia để trị là gì?

NỘI DUNG BÀI VIẾT

Giới thiệu

Trong bài viết này, bạn sẽ tìm hiểu cách hoạt động của thuật toán chia để trị. Ngoài ra, bạn sẽ tìm thấy sự so khác nhau giữa thuật toán chia để trị và các thuật toán khác để giải quyết một bài toán đệ quy.

Thuật toán chia để trị (Divide and Conquer) là một phương pháp để giải quyết một vấn đề lớn bằng cách:

Chia vấn đề thành các vấn đề nhỏ hơn
Giải quyết các vấn đề nhỏ
Kết hợp chúng để có được lời giải mong muốn.

Để sử dụng các thuật toán chia để trị, đệ quy thường được sử dụng. Tìm hiểu về đệ quy tại đây.

Thuật toán chia để trị hoạt động như thế nào?

Dưới đây là các bước chính:

Chia: Chia bài toán đã cho thành các bài toán nhỏ bằng cách sử dụng đệ quy.
Trị: Giải các bài toán nhỏ đó bằng cách sử dụng đệ quy. Nếu bài toán đó đủ nhỏ, hãy giải trực tiếp.
Kết hợp: Kết hợp các lời giải của các bài toán con là một phần của quá trình đệ quy để có được lời giải cho bài toán thực tế.

Hãy để mình giải thích khái niệm này cho các bạn thông qua các ví dụ nhé!

Ở đây, chúng ta sẽ sắp xếp một mảng bằng cách sử dụng phương pháp chia để trị (VD: Merge Sort).

Bước 1: Cho 1 mảng như sau:

Bước 2: Chia mảng thành 2 phần:

Tiếp tục, đệ quy mỗi phần thành 2 nửa cho đến khi nào không thể đệ quy nữa thì dừng.

Bước 3: Bây giờ, hãy kết hợp các phần tử riêng lẻ theo cách được sắp xếp. Tại đây, hãy trị và kết hợp các bước song song.

Độ phức tạp của thuật toán

Độ phức tạp của thuật toán chia để trị và thu được tính bằng cách sử dụng định lý chính.

T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed to have the same size.
f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions

Chúng ta hãy lấy một ví dụ để tìm độ phức tạp về thời gian của một bài toán đệ quy.

Đối với sắp xếp trộn, biểu thức có thể được viết dưới dạng:

T(n) = aT(n/b) + f(n)
     = 2T(n/2) + O(n)
Where, 
a = 2 (each time, a problem is divided into 2 subproblems)
n/b = n/2 (size of each sub problem is half of the input)
f(n) = time taken to divide the problem and merging the subproblems
T(n/2) = O(n log n) (To understand this, please refer to the master theorem.)

Now, T(n) = 2T(n log n) + O(n)
          ≈ O(n log n)

So sánh chia để trị và quy hoạch động

Thuật toán chia để trị là chia một vấn đề thành các bài toán con nhỏ hơn, các bài toán con này tiếp tục được giải một cách đệ quy. Kết quả của mỗi bài toán con không được lưu trữ để tham khảo trong tương lai, ngược lại, trong quy hoạch động, kết quả của mỗi bài toán con được lưu trữ để tham khảo trong tương lai.

Sử dụng phương pháp chia để trị khi cùng một bài toán con không được giải nhiều lần. Sử dụng phương pháp quy hoạch động khi kết quả của một bài toán con sẽ được sử dụng lại nhiều lần trong tương lai.

Hãy xem qua ví dụ dưới đây. Giả sử, chúng ta đang cố gắng tìm chuỗi Fibonacci. Sau đó:

Chia để trị:

fib(n)
    If n < 2, return 1
    Else , return f(n - 1) + f(n -2)

Quy hoạch động:

mem = [ ]
fib(n)
    If n in mem: return mem[n] 
    else,     
        If n < 2, f = 1
        else , f = f(n - 1) + f(n -2)
        mem[n] = f
        return f

Trong quy hoạch động, mem lưu trữ kết quả của bài toán con.

Lợi ích của thuật toán chia để trị

Độ phức tạp đối với nhân hai ma trận bằng phương pháp tuyến tính là O(n³), trong khi sử dụng phương pháp chia để trị (tức là nhân ma trận Strassen) là O(n^2.8074). Các vấn đề khác như Tháp Hà Nội cũng được đơn giản hóa bằng phương pháp này.
Và phương pháp này cũng phù hợp với các hệ thống đa xử lý.
Hiệu quả hơn khi sử dụng bộ nhớ đệm.

Ứng dụng của thuật toán chia để trị

Binary Search (Tìm kiếm nhị phân)
Merge Sort (Sắp xếp trộn)
Quick Sort (Sắp xếp nhanh)
Strassen’s Matrix multiplication (Nhân ma trận Strassen)
Karatsuba Algorithm (Thuật toán Karatsuba)

Cảm ơn bạn đã theo dõi bài viết!

Các bạn có thể tham khảo các bài viết hay về JavaScript tại đây.

Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.

TỔNG HỢP TÀI LIỆU HỌC LẬP TRÌNH CƠ BẢN CHO NGƯỜI MỚI BẮT ĐẦU
KHOÁ HỌC BOOTCAMP JAVA/PHP/.NET TRỞ THÀNH LẬP TRÌNH VIÊN TRONG 5-6 THÁNG

Thuật toán chia để trị là gì?

Giới thiệu