Chia để trị

Wiki › Thuật toán

huunguyen · Last updated 28, Tháng 3, 2026, 22:49

Chia để trị (Divide and Conquer) giải bài toán bằng cách:

Chia bài toán thành các bài toán con nhỏ hơn cùng dạng.
Trị (giải) các bài toán con đệ quy.
Kết hợp kết quả để ra đáp án.

Độ phức tạp — Master Theorem

Với công thức đệ quy $T (N) = a T (N / b) + O (N^{d})$ :

Điều kiện	Độ phức tạp
$d > \log_{b} a$	$O (N^{d})$
$d = \log_{b} a$	$O (N^{d} \log N)$
$d < \log_{b} a$	$O (N^{\log_{b} a})$

Ví dụ 1: Merge Sort

Sắp xếp mảng bằng cách chia đôi, sắp xếp hai nửa, rồi trộn lại — $O (N \log N)$ .

void merge_sort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(a, l, mid);
    merge_sort(a, mid+1, r);

    // Trộn hai nửa đã sắp xếp
    vector<int> tmp;
    int i = l, j = mid+1;
    while (i <= mid && j <= r)
        tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= r) tmp.push_back(a[j++]);
    for (int k = l; k <= r; k++) a[k] = tmp[k-l];
}

Ví dụ 2: Tìm kiếm nhị phân

Chia đôi mảng đã sắp xếp mỗi bước — $O (\log N)$ .

int binary_search(vector<int>& a, int l, int r, int target) {
    if (l > r) return -1;
    int mid = (l + r) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) return binary_search(a, mid+1, r, target);
    return binary_search(a, l, mid-1, target);
}

Ví dụ 3: Đếm nghịch thế (Inversion Count)

Đếm số cặp $(i, j)$ với $i < j$ mà $a [i] > a [j]$ — $O (N \log N)$ .

long long merge_count(vector<int>& a, int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) / 2;
    long long cnt = merge_count(a, l, mid) + merge_count(a, mid+1, r);

    vector<int> tmp;
    int i = l, j = mid+1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) { tmp.push_back(a[i++]); }
        else {
            cnt += mid - i + 1;  // a[i..mid] đều > a[j]
            tmp.push_back(a[j++]);
        }
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= r) tmp.push_back(a[j++]);
    for (int k = l; k <= r; k++) a[k] = tmp[k-l];
    return cnt;
}

Ví dụ 4: Lũy thừa nhanh (Fast Power)

Tính $a^{n} \mod m$ trong $O (\log n)$ .

long long power(long long a, long long n, long long mod) {
    if (n == 0) return 1;
    long long half = power(a, n/2, mod);
    long long res = half * half % mod;
    if (n % 2 == 1) res = res * a % mod;
    return res;
}

def power(a, n, mod):
    if n == 0: return 1
    half = power(a, n // 2, mod)
    res = half * half % mod
    if n % 2 == 1: res = res * a % mod
    return res

# Hoặc dùng built-in Python
pow(a, n, mod)  # O(log n)

Các dạng bài thường gặp

Merge Sort, Quick Sort
Tìm kiếm nhị phân
Lũy thừa nhanh
Đếm nghịch thế
Closest pair of points
Karatsuba multiplication

Bình luận

Không có bình luận tại thời điểm này.