¶ Chia để trị (Divide and Conquer)
Tác giả:
- Nguyễn Đức Kiên, Trường Đại học Công nghệ, ĐHQGHN
Reviewer:
- Nguyễn Hoàng Vũ - Trường Đại học Công nghệ, ĐHQGHN
- Nguyễn Minh Nhật - THPT chuyên Khoa học Tự nhiên, ĐHQGHN
¶ Mở đầu
Chia để trị (Divide and Conquer, DnC) chỉ việc chia nhỏ bài toán thành các phần nhỏ có cùng dạng với nó, tới khi có thể giải được một cách dễ dàng (thường là có ngay kết quả), sau đó dùng các kết quả này kết hợp lại để giải được bài toán lớn. Các bước để giải một bài toán chia để trị bao gồm:
- Chia bài toán thành các bài toán con (thường là chia đôi hoặc xấp xỉ như vậy).
- Giải các bài toán con. Nếu vẫn gặp khó khăn với các bài toán con, ta lại tiếp tục chia nó thành các bài toán nhỏ hơn cho tới khi dễ dàng tìm được kết quả.
- Tổng hợp kết quả các bài toán con lại để có kết quả của bài toán lớn nếu cần.
Bạn đọc có thể thấy những bước trên có phần tương đồng với quá trình làm các bài toán đệ quy cơ bản. Các bài toán đó cũng có thể coi là chia để trị, và đệ quy cũng là một cách để cài đặt các thuật chia để trị.
Tư tưởng chia để trị cũng xuất hiện rất đa dạng và phổ biến trong các bài toán, thuật toán và cấu trúc dữ liệu: tìm kiếm nhị phân, cấp trúc cây tìm kiếm nhị phân (BST), heap, cây phân đoạn (segment tree), cây BIT/Fenwick, mảng thưa, các thuật toán sắp xếp, luỹ thừa nhanh, ...
¶ Xác định độ phức tạp
Ta nhắc lại một vài ký hiệu trước khi vào phần này:
- : Logarit cơ số của , là số thực thoả mãn . Bài viết này sẽ sử dụng ký hiệu cho trường hợp .
- : Thời gian chạy thuật toán với kích thước dữ liệu đầu vào là , tính bằng số phép tính.
- (big-O): Các hàm độ phức tạp thuật toán. Chi tiết bạn đọc tham khảo Độ phức tạp thời gian
Chi tiết về các ký hiệu độ phức tạp và thời gian bạn đọc có thể tham khảo bài .
¶ Định lý Thợ (Master theorem)
Các công thức dưới đây được nhắc đến trong sách Introduction to Algorithms (xem phần Tài liệu tham khảo). Chưa rõ tên tiếng Việt của thuật toán có nguồn gốc từ đâu.
Độ phức tạp của các thuật toán chia để trị cài đặt dưới dạng đệ quy được xác định bằng Định lý Thợ.
Giả sử có một bài toán với dữ liệu đầu vào có độ lớn là (mảng có độ dài chẳng hạn) được cài đặt bằng đệ quy, tại mỗi vòng đệ quy bài toán được chia thành bài toán con như sau:
void P(<input kích thước n>)
{
if (n < k) //k là một hằng số
{
<giải bài toán trực tiếp (base case)>
}
else
{
for (int i = 1; i <= a; i ++)
{
P(<input kích thước n/b>);
}
<kết hợp kết quả các bước trên>
}
}
Nếu ta coi mỗi bài toán con là một nút trên một cây và mỗi lần gọi đệ quy từ một bài toán con ta nối thêm một nút con vào nút biểu diễn bài toán nói trên thì bài toán lớn của chúng ta sẽ có dạng như sau:
Tại mỗi nút của cây trên, nếu việc kết hợp kết quả các bài toán con mất thời gian, thì thời gian chạy tại một nút với kích thước dữ liệu là có thể được tính theo công thức truy hồi:
với là một hằng số nào đó, tuỳ thuộc vào thuật toán.
Ví dụ, với thuật toán MergeSort, tại mỗi bước ta chia một đoạn có độ dài thành hai đoạn con có độ dài hoặc xấp xỉ số đó. Thuật toán sẽ có thời gian chạy là khi và khi .
Bây giờ, ta lại xét giá trị . Giả sử viết được dưới dạng (Định lý Thợ chỉ áp dụng khi có độ phức tạp đa thức). Chúng ta có thể tiếp tục thu gọn biểu thức như sau:
| Quan hệ và | Biểu thức |
|---|---|
| khi khi khi |
|
| khi khi |
Một số ví dụ:
- Thuật toán Tìm kiếm nhị phân (Binary search) mỗi lần chia bài toán thành 2 phần bằng nhau nhưng chỉ xét 1, không cần kết hợp kết quả sẽ có . Thời gian chạy trung bình của thuật toán là , ứng với .
- Thuật toán MergeSort chia đôi dãy hiện tại thành 2 phần bằng nhau, lấy cả 2 và phải xét lại cả 2 phần để lấy kết quả sẽ có . Thời gian chạy trung bình của thuật toán là , ứng với (Chi tiết về thuật MergeSort bạn đọc có thể đọc phần dưới).
- Một thuật toán chia để trị có . Thời gian chạy trung bình của thuật toán là , tương ứng với .
Định lý Thợ là một công cụ hữu hiệu để xác định độ phức tạp của một thuật toán chia để trị. Chỉ cần xác định được số bài toán con, kích thước dữ liệu các bài toán con và độ phức tạp của việc kết hợp dữ liệu, ta dễ dàng tìm ra độ phức tạp chung của bài toán.
¶ Một số ví dụ áp dụng Chia để trị
Các bài toán áp dụng Chia để trị chỉ có chung một phương pháp như đã nói ở trên. Khi sử dụng, thứ mà ta quan tâm chủ yếu là độ phức tạp; thông thường, chia để trị là công cụ tối ưu độ phức tạp khá hiệu quả.
¶ MergeSort
Đề bài: Sắp xếp một dãy gồm số nguyên .
¶ Phân tích thuật toán
Đây là một thuật toán sắp xếp nổi tiếng và cũng hay được áp dụng (nếu không được phép sử dụng các thư viện có sẵn). Thuật toán này sử dụng phương pháp đệ quy. Tại mỗi vòng đệ quy, giả sử đang cần sắp xếp một đoạn ta chia dãy làm hai phần bằng nhau, và với . Sau khi đã gọi đệ quy các đoạn con, ta tiến hành hợp nhất hai đoạn này. Việc hợp nhất hai đoạn đã sắp xếp được tiến hành bằng phương pháp hai con trỏ, có độ phức tạp là . Trong trường hợp một đoạn chỉ có một phần tử duy nhất, ta coi như nó đã được sắp xếp.
¶ Cài đặt
Nhấn để hiện code
//Ghép hai đoạn [l1, r1], [l2, r2] thành một đoạn bắt đầu từ l1
void merge(int a[], int l1, int r1, int l2, int r2)
{
int cur = l2;
vector <int> newArr;
for (int i = l1; i <= r1; i++)
{
while (cur <= r2 && a[cur] < a[i])
{
newArr.push_back(a[cur]);
cur++;
}
newArr.push_back(a[i]);
}
for (int j = cur; j <= r2; j ++) newArr.push_back(a[j]);
for (int i = 0; i < newArr.size(); i ++) a[l1 + i] = newArr[i];
}
void mergeSort(int a[], int l, int r)
{
if (l == r) return;
int mid = (l + r) / 2;
mergeSort(a, l, mid);
mergeSort(a, mid + 1, r);
merge(a, l, mid, mid + 1, r);
}
Hàm merge() trong đoạn code trên có thể thay thế bằng hàm merge() trong thư viện algorithm.
¶ Đánh giá
Theo như phân tích độ phức tạp đã đề cập ở trên, độ phức tạp trung bình của MergeSort là . Thực tế thì trong mọi trường hợp, độ phức tạp của MergeSort luôn là .
¶ Cặp điểm gần nhất
Đề bài: Cho điểm trên mặt phẳng . Hãy tìm khoảng cách nhỏ nhất giữa hai điểm bất kỳ trong đó.
Đề bài VNOI: NEAREST
¶ Phân tích
Giả sử có điểm .
Ta có thể sử dụng một thuật toán "ngây thơ" cho bài này: xét tất cả mọi cặp điểm, kiểm tra xem khoảng cách giữa hai cặp điểm nào là gần nhau nhất. Độ phức tạp khi đó sẽ là trong mọi trường hợp, chưa đủ để vượt qua giới hạn của bài toán này.
Ta nghĩ đến việc sử dụng chia để trị. Trước hết, ta sắp xếp các điểm trong tập hợp theo hoành độ . Tại mỗi vòng đệ quy, ta chia tập điểm hiện tại thành hai phần bên trái và bên phải vị trí ta chọn. Base case (trường hợp cơ bản) lúc này thay vì là thì sẽ là , do ta không thể xác định khoảng cách với điểm, và cũng cần đảm bảo rằng khi chạy đệ quy không tồn tại tập nào có độ lớn như vậy. Ngoài trường hợp đó, ta thu được kết quả của 2 tập trái và phải. Tuy nhiên, việc kết hợp kết quả không đơn giản, vì một điểm ở bên trái vẫn có thể tạo ra khoảng cách ngắn nhất với một điểm bên phải. Ta cũng không thể chạy hết từng cặp điểm một trong hai tập này, vì khi đó theo Định lý Thợ độ phức tạp trung bình sẽ lên đến .
Ở hình vẽ trên, hai màu xanh và đỏ tượng trưng cho hai nửa phải và trái. Điểm đóng vai trò là , thuộc tập bên phải.
Gọi là giá trị nhỏ hơn giữa khoảng cách ngắn nhất giữa hai điểm ta vừa thu được ở tập bên phải và tập bên trái. Cụ thể:
Khi đó, trong cùng một tập hợp, không tồn tại một cặp điểm nào có khoảng cách ngắn hơn . Giữa hai tập hợp lúc này ta sẽ chỉ quan tâm đến các cặp điểm có khoảng cách nhỏ hơn .
Xét các điểm có hoành độ cách một khoảng không vượt quá . Các điểm này nằm giữa các đường thẳng và :
Đến đây, ta có một nhận xét quan trọng: Với mỗi điểm nằm trong miền nằm giữa hai đường thẳng nói trên (vùng được tô màu), tồn tại không quá 7 điểm khác có tung độ lớn hơn không quá so với .
Chứng minh (nhấn để hiện)
Khoảng các điểm thoả mãn điều kiện trên được giới hạn bởi hình vẽ sau:
Khoảng trên là hình tạo bởi hai hình vuông có cạnh là nằm cạnh nhau. Các điểm thoả mãn nằm trong hoặc trên cạnh của hai hình vuông này, và khoảng cách giữa hai điểm bất kỳ trong cùng một hình vuông không nhỏ hơn . Không thể xếp quá điểm như vậy vào trong một hình vuông. Thật vậy, với mỗi điểm ta vẽ một đường tròn có tâm tại điểm đó và bán kính bằng . Hai đường tròn bất kỳ không thể có nhiều hơn 1 điểm chung, vì nếu không khoảng cách giữa chúng sẽ nhỏ hơn .
Ta thấy mỗi hình tròn có diện tích giao với hình vuông là , do khi tịnh tiến hình tròn dọc theo cả hai phương và ta đều thu được các hình có diện tích lớn hơn. Vì hình vuông có diện tích là , số miền diện tích như vậy có thể đặt vào hình tròn là . Tuy nhiên, không tồn tại cách đặt 5 điểm vào hình vuông thoả mãn yêu cầu của đề bài, nên số điểm đặt được tối đa là 4.
Với 4 điểm ở mỗi hình vuông, số điểm đặt được tối đa là 8, tính cả điểm mà chúng ta đã xét ban đầu. Do vậy có tối đa 7 điểm thoả mãn tung độ lớn hơn không quá .
Nếu ta sắp xếp các điểm trong miền này theo thứ tự tăng dần, với một điểm bất kỳ ta chỉ cần xét một số điểm lân cận thoả mãn chênh lệch tung độ không vượt quá , rồi tính khoảng cách giữa chúng.
Khi cài đặt, sau khi tiến hành tìm khoảng cách ngắn nhất giữa hai điểm ta có thể giữ nguyên trạng thái sau khi sắp xếp theo của đoạn đó, rồi dùng phép merge() như bài MergeSort ở trên để sắp xếp nhanh đoạn lớn trong .
¶ Cài đặt
Nhấn để hiện code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const long long INF = LLONG_MAX;
struct Point
{
double x, y;
void inp()
{
cin >> x >> y;
}
bool operator < (Point other)
{
if (x == other.x) return (y < other.y);
return (x < other.x);
}
}a[MAXN], middleArea[MAXN];
bool ascendingY(Point p1, Point p2) {return make_pair(p1.y, p1.x) < make_pair(p2.y, p2.x);}
double dist(Point p1, Point p2)
{
return hypot(1.0 * p1.x - p2.x, 1.0 * p1.y - p2.y);
}
//Tìm cặp điểm gần nhất trong các điểm thuộc middleAreaa
double nearestMiddle(int middleAreaSize, double d)
{
double ret = INT_MAX;
for (int i = 1; i <= middleAreaSize; i++)
for (int j = i + 1; j <= middleAreaSize; j++)
{
if (middleArea[j].y - middleArea[i].y >= d) break;
ret = min(ret, dist(middleArea[i], middleArea[j]));
}
return ret;
}
//Tìm cặp điểm gần nhất trong các điểm thuộc mảng a độ dài n
double nearest(Point a[], int n)
{
if (n <= 3)
{
sort(a + 1, a + n + 1, ascendingY);
double ret = INF;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
ret = min(ret, dist(a[i], a[j]));
return ret;
}
int mid = n / 2;
auto midPoint = a[mid];
double dL = nearest(a, mid);
double dR = nearest(a + mid, n - mid);
double d = min(dL, dR);
int middleAreaSize = 0;
merge(a + 1, a + mid + 1, a + mid + 1, a + n + 1, middleArea + 1, ascendingY);
for (int i = 1; i <= n; i ++)
{
a[i] = middleArea[i];
if (abs(middleArea[i].x - midPoint.x) < d) middleArea[++middleAreaSize] = middleArea[i];
}
return min(d, nearestMiddle(middleAreaSize, d));
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++) a[i].inp();
sort(a + 1, a + n + 1);
cout << fixed << setprecision(3) << nearest(a, n);
return 0;
}
Mảng middleArea[] lưu các điểm nằm ở giữa miền tạo bởi hai đường thẳng và .
Hàm hypot(a, b) trả về cạnh huyền của tam giác vuông có hai cạnh góc vuông là và , tức giá trị ; hàm này có sẵn trong thư viện cmath.
¶ Đánh giá
Mỗi tập được chia thành hai tập con, mỗi tập con có bộ dữ liệu bằng đúng một nửa tập lớn. Việc tìm kết quả của đoạn lớn bao gồm việc ghép đoạn để sắp xếp lại mất và tính khoảng cách nhỏ nhất giữa các điểm ở giữa hết . Do vậy thuật này có và có độ phức tạp trung bình là theo Định lý Thợ. Trong mọi trường hợp, thuật toán đều thực hiện những bước tương tự và độ phức tạp là .
¶ Bonus
Bài toán này còn một lời giải khác bằng cách sử dụng kỹ thuật đường quét (sweep-line) kết hợp với cấu trúc set. Lời giải này có cùng độ phức tạp nhưng ngắn gọn và dễ cài đặt hơn lời giải bằng chia để trị. Bạn đọc tự cài đặt và tìm hiểu thêm, tham khảo code của skyvn97.
¶ Bài toán Truy vấn trên mảng cố định
¶ Bài toán
Bài toán Truy vấn trên mảng cố định (SRQ - Static Array Queries) được mô tả như sau:
Xét phép toán bất kỳ và mảng gồm các số . Ta phải trả lời truy vấn, mỗi truy vấn yêu cầu ta tính , với là các giá trị cho trước, .
Trong trường hợp là phép toán có tính chất kết hợp, cụ thể hơn, phép toán này áp dụng được trên các giá trị (không nhất thiết là số) sao cho , ta có thể sử dụng chia để trị để giải. Một số ví dụ cho phép toán này là phép cộng, phép nhân, phép lấy .
¶ Thuật toán giải
Có rất nhiều cách giải bài toán này với độ phức tạp không gian và thời gian logarit tuyến tính (), như cây phân đoạn, BIT, mảng thưa, ... Chia để trị cũng là một cách hiệu quả để giải quyết bài toán, đặc biệt trong trường hợp độ phức tạp cho mỗi truy vấn cần rất thấp.
Giả sử tất cả các truy vấn đều thoả mãn điều kiện . Ban đầu, ta có . Đặt (tuỳ trường hợp, để tính toán thuận lợi, có thể nhận các giá trị khác nhau, nhưng thường ta lấy vị trí chính giữa). Gọi là "tổng" hậu tố tính từ tới hay:
Tương tự, ta gọi là "tổng" tiền tố tính từ tới :
Với các truy vấn thoả mãn , kết quả của truy vấn đó sẽ là . Điều này là hiển nhiên theo tính chất kết hợp. Với các truy vấn còn lại, hiển nhiên chúng chỉ nằm hoàn toàn ở một trong hai bên của . Ta thay đổi các giá trị và tính các giá trị theo mới. Cứ như vậy tới khi .
Về độ phức tạp, ở mỗi bước ta chia mảng độ dài thành 2 phần đều nhau có kích thước dữ liệu là . Sau khi có hai đoạn này, ta mất để tính , và cho mỗi truy vấn, tổng cộng là . Độ phức tạp thời gian của thuật toán là , chạy ổn định, còn về không gian chỉ cần .
Hai mảng và không có chung nhau một vị trí nào, vậy nên ta có thể kết hợp lại thành một mảng . Khi đó với một đoạn có phần tử ở giữa là , các giá trị từ đến tương đương với , và các giá trị đến tương đương với .
Nếu phải sử dụng các truy vấn online, ta lưu lại của mỗi lần đệ quy dưới dạng một mảng hai chiều giống như mảng thưa, ví dụ là kết quả ở vòng đệ quy với độ sâu (xem ví dụ để hiểu rõ hơn). Bằng cách này, ta vẫn có thể trả lời mọi truy vấn trong , và độ phức tạp trở thành cho thời gian và cho không gian.
¶ Ví dụ
Đề bài: SEGPROD
Tóm tắt: Cho dãy gồm số nguyên dương và một số nguyên dương . Có truy vấn, truy vấn thứ yêu cầu tìm tích của các số với , lấy số dư khi chia cho . Chú ý rằng các truy vấn phải được xử lý online và số có thể không là số nguyên tố.
¶ Phân tích
Đây là một bài toán SRQ khá "thẳng", chỉ yêu cầu ta tính tích trên một đoạn bất kỳ. Ý tưởng "ngây thơ" nhất là duyệt qua mọi đoạn con được truy vấn để tìm tích của nó, mất . Ta cũng nghĩ đến việc áp dụng tích tiền tố đơn giản, tuy nhiên việc lấy ra một đoạn sẽ gặp khó khăn nếu không phải là số nguyên tố. Các ý tưởng khác cho bài toán SRQ như cây phân đoạn và mảng thưa đều mất cho mỗi truy vấn, khó qua được giới hạn của bài toán này. May mắn thay, sử dụng chia để trị vừa khít với bộ dữ liệu của bài toán.
Bằng cách sử dụng cách chia để trị như đã nói ở trên, ta dễ dàng khởi tạo mảng trong . Khi trả lời một truy vấn lq rq, như đã nói ở trường hợp truy vấn offline, và phải thoả mãn và tại một vòng đệ quy.
Giả sử độ sâu của một vòng đệ quy là số lần phải gọi đệ quy từ đoạn , ta thấy hai đoạn có cùng độ sâu không có điểm chung. Do đó ta có thể lưu các giá trị đi kèm với độ sâu mà không sợ bị trùng lặp.
Quay lại với truy vấn lq rq, ta cần phải tìm một độ sâu sao cho và nằm về hai phía của của độ sâu này. Để giải quyết vấn đề này, ta gọi là một dãy bit, sao cho bit thứ của dãy này bằng nếu vị trí nằm về bên trái (tính cả ) ở độ sâu , và nếu vị trí này nằm về bên phải của (không tính ). Ví dụ với dãy bằng như trên hình, , . Như vậy, độ sâu thoả mãn và nằm về hai phía của ở độ sâu này là vị trí của bit đầu tiên bằng từ phải qua trái trong dãy , với là phép xor.
¶ Cài đặt
Nhấn để hiện code
const int MAXN = 1e6;
int n, a[MAXN], b[MAXN], mod, acc[21][MAXN], mask[MAXN];
/// Khởi tạo acc
void calc(int l, int r, int level)
{
if (l == r) return;
int mid = (l + r) / 2;
calc(l, mid, level + 1);
calc(mid + 1, r, level + 1);
acc[level][mid] = a[mid];
for (int i = mid - 1; i >= l; i --)
acc[level][i] = 1ll * acc[level][i + 1] * a[i] % mod;
acc[level][mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; i ++)
acc[level][i] = 1ll * acc[level][i - 1] * a[i] % mod;
for (int i = mid + 1; i <= r; i ++) mask[i] |= (1 << level);
}
/// Giải quyết 1 truy vấn
void solve()
{
int q;
cin >> n >> mod >> q;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++)
for (int l = 0; (1 << l) < n; l++)
acc[l][i] = 1;
for (int i = 0; i < n; i ++) mask[i] = 0;
calc(0, n - 1, 0);
int res = 0;
for (int i = 0; i < q / 64 + 2; i++)
{
cin >> b[i];
}
for (int i = 0, lq = 0, rq = 0; i < q; i++)
{
// Nhận truy vấn tiếp theo theo cách đề bài mô tả
if (i % 64 == 0)
{
lq = (b[i / 64] + res) % n;
rq = (b[i / 64 + 1] + res) % n;
}
else
{
lq = (lq + res) % n;
rq = (rq + res) % n;
}
if (lq > rq) swap(lq, rq);
// Tìm kết quả cho đoạn [lq, rq] vừa tìm được
if (lq == rq) res = a[lq];
else
{
int lvl = __builtin_ctz(mask[lq] ^ mask[rq]);
res = 1ll * acc[lvl][lq] * acc[lvl][rq] % mod;
}
(res += 1) %= mod;
}
cout << res << "\n";
}
Hàm __builtin_ctz(x) trả về số bit ở cuối dãy nhị phân có giá trị bằng . Giá trị này chính là vị trí của bit đầu tiên từ phải qua trái của dãy. Bạn đọc có thể xem bài Phép toán bit để biết thêm chi tiết.
¶ Chú ý thêm
- Kỹ thuật chia để trị có thể làm tối ưu khá tốt lời giải của một thuật toán. Đặc biệt trong các bài toán quy hoạch động, chia để trị là một trick tối ưu khá hiệu quả. Bạn đọc có thể tham khảo thêm tại bài viết này.
- Đối với các bài toán SRQ, còn một phương pháp hiệu quả vượt trội các phương pháp đã nói trên về độ phức tạp thời gian, đó là cấu trúc Sqrt Tree. Bạn đọc có thể tìm hiểu thêm về cấu trúc này tại đây.
¶ Bài tập
Các bài chia để trị nói chung:
Các bài toán SRQ:
- VNOJ - XORSHIFT
- Duyên hải Bắc Bộ 2023 - HKDATA (Bạn cần tham gia contest để xem được đề bài)
- DMOJ - Continued Fractions
- USACO - Non-Decreasing Subsequences
- Codeforces - Destiny
- Codeforces - Timofey and our friends animals
¶ Tài liệu tham khảo
- Steven Halim, Felix Halim (2013), Competitive Programing 3
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2022), Introduction to Algorithms, 4th edition
- Mark Berg , Otfried Cheong , Marc Kreveld , Mark Overmars (2008), Computational Geometry - Algorithms and Applications
- Wikipedia (Master's Theorem)
- Bài giảng của Piotr Indyk tại MIT (bài NEAREST)
- USACO Guide Platinium, Divide and Conquer - SRQ
- Codeforces, Post của Wind_Eagle
- Codeforces, Post của steveonalex