🧠

Giải thuật

Giải thuật là công cụ để giải bài toán hiệu quả. Đánh giá qua Big-O: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n).

1. Tìm kiếm tuyến tính vs nhị phân

Tuyến tính O(n) — mọi mảng. Nhị phân O(log n) — chỉ mảng đã sắp xếp. STL: lower_bound, upper_bound, binary_search.

2. Các thuật toán sắp xếp

Bubble/Selection/Insertion: O(n²), dễ viết. Merge Sort, Quick Sort, Heap Sort: O(n log n). STL sort() = IntroSort (hybrid), O(n log n).

3. Chia để trị (Divide & Conquer)

Chia bài toán thành phần nhỏ, giải, rồi ghép. Ví dụ: Merge Sort, Quick Sort, tìm cặp gần nhất.

4. Tham lam (Greedy)

Chọn tốt nhất tại mỗi bước cục bộ. Ví dụ: trả tiền lẻ, xếp lịch, Huffman.

5. Quy hoạch động (DP)

Chia bài toán con, lưu kết quả (memoization/tabulation) tránh tính lại. Ví dụ: Fibonacci DP, ba lô, LCS, LIS.

💻 Code mẫu thực chiến

Fibonacci DP - từ O(2^n) về O(n)

Đệ quy thuần vượt time; DP tuyến tính.

long long fib[100];
fib[0] = 0; fib[1] = 1;
for (int i = 2; i < 100; i++) fib[i] = fib[i-1] + fib[i-2];

Đổi tiền tham lam

Với hệ tiền chuẩn (VN: 500k, 200k, 100k, 50k, …), tham lam tối ưu.

int menh[] = {500000, 200000, 100000, 50000, 20000, 10000, 5000, 2000, 1000};
int tien; cin >> tien;
for (int m : menh) {
    int sl = tien / m;
    if (sl > 0) cout << m << ": " << sl << " to\n";
    tien %= m;
}

Bài toán ba lô 0/1 (DP)

Chọn đồ vật (w, v) để max giá trị với sức chứa W.

int knapsack(vector<int>& w, vector<int>& v, int W) {
    int n = w.size();
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= w[i-1])
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]);
        }
    return dp[n][W];
}

💡 Mẹo & lưu ý

Ước lượng độ phức tạp trước khi code: n=10^6 chỉ chấp nhận O(n log n) trở xuống.
Dùng STL trước khi tự cài — nhanh và ít bug.
DP: nhận diện khi bài có bài toán con lặp lại và cấu trúc con tối ưu.

🎯 Luyện tập chủ đề này Chủ đề khác