Chương 01

Nền Tảng Trọng Tâm
Để Tối Ưu Thuật Toán

Trước khi bước vào bất kỳ thuật toán sắp xếp nào, bạn cần nắm vững các khái niệm nền tảng — đây chính là "la bàn" giúp bạn chọn đúng công cụ cho từng bài toán.

📊 Phân tích Độ phức tạp Thời gian & Không gian

Độ phức tạp là cách chúng ta đánh giá hiệu năng của thuật toán khi dữ liệu đầu vào tăng lên. Thay vì đo thời gian chạy cụ thể (phụ thuộc máy), ta đánh giá qua số phép toán cơ bản theo kích thước đầu vào n.

🔑 Ký hiệu Big-O — Những mức phổ biến

Big-OTên gọiVí dụN=10⁶Đánh giá
O(1)Hằng sốTruy cập mảng a[i]1⚡ Tuyệt vời
O(log n)LogaritBinary Search~20⚡ Rất nhanh
O(n)Tuyến tínhDuyệt mảng 1 lần10⁶✅ Tốt
O(n log n)Log-tuyến tínhMerge Sort, HeapSort~2×10⁷✅ Tốt
O(n²)Bình phươngInsertion Sort10¹²⚠️ Chậm
O(2ⁿ)MũBrute-force tập con∞❌ Không khả thi
💡 Mẹo thực chiến

Với giới hạn N ≤ 10⁵ ~ 10⁶: thuật toán O(n log n) là bắt buộc. Nếu N ≤ 10³: O(n²) vẫn chấp nhận được. Luôn nhìn giới hạn đề bài trước khi chọn thuật toán!

📦 Độ phức tạp Không gian (Space Complexity)

Ngoài thời gian, ta còn quan tâm bộ nhớ phụ mà thuật toán sử dụng. Ví dụ: Merge Sort cần mảng phụ O(n), trong khi Insertion Sort chỉ cần O(1) bộ nhớ thêm (in-place).

In-place

Chỉ dùng O(1) bộ nhớ phụ. Ví dụ: Insertion Sort, Selection Sort, HeapSort

Not In-place

Cần bộ nhớ phụ O(n). Ví dụ: Merge Sort, Counting Sort

⚖️ Tính ổn định (Stability) trong Sắp xếp

Một thuật toán sắp xếp được gọi là ổn định (stable) nếu nó giữ nguyên thứ tự tương đối của các phần tử có giá trị bằng nhau.

🃏 Ví dụ trực quan: Sắp xếp lá bài

Giả sử ta có các lá bài: 5♠ 3♥ 3♠ 2♦ 5♥ — sắp xếp theo giá trị số.

✅ Stable Sort

2♦ 3♥ 3♠ 5♠ 5♥

3♥ vẫn đứng trước 3♠ (giữ nguyên thứ tự ban đầu)

❌ Unstable Sort

2♦ 3♠ 3♥ 5♥ 5♠

3♠ lại đứng trước 3♥ (thứ tự bị đảo)

Tại sao Stability quan trọng?

Khi sắp xếp đa tiêu chí (ví dụ: sắp theo điểm, rồi theo tên), thuật toán stable đảm bảo tiêu chí trước đó không bị phá vỡ.

Thuật toánStable?
Insertion Sort✅ Có
Merge Sort✅ Có
Counting Sort✅ Có
Selection Sort❌ Không
QuickSort❌ Không
HeapSort❌ Không

⚡ Tối ưu Luồng Nhập/Xuất (Fast I/O) trong C++

Một trong những lỗi phổ biến nhất khi thi lập trình là Time Limit Exceeded (TLE) dù thuật toán đúng. Nguyên nhân thường gặp: cin/cout quá chậm so với scanf/printf.

⚡ C++ — Fast I/O Template 
#include <bits/stdc++.h>
using namespace std;

int main() {
    // === Fast I/O — LUÔN đặt ở đầu main() ===
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // Sử dụng thư viện <algorithm>
    sort(a.begin(), a.end());

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}
⚠️ Lưu ý quan trọng

Sau khi dùng ios_base::sync_with_stdio(false), KHÔNG được trộn lẫn cin/cout với scanf/printf. Chọn một trong hai!

Giải thích từng dòng

  • ios_base::sync_with_stdio(false) — Tắt đồng bộ giữa C stdio và C++ iostream → tăng tốc đáng kể
  • cin.tie(NULL) — Tách cin khỏi cout → không tự động flush trước mỗi lần đọc
  • '\n' thay vì endl — endl force flush buffer, chậm hơn nhiều

🔗 So sánh: Mảng (Array) vs Danh sách liên kết đơn (Linked List)

Hai cấu trúc dữ liệu nền tảng nhất trong lập trình. Hiểu rõ bản chất lưu trữ của chúng sẽ giúp bạn chọn đúng cấu trúc cho từng bài toán.

📦 Mảng (Array) — Bộ nhớ liên tục
10
25
7
42
18
[0]
[1]
[2]
[3]
[4]

Các phần tử nằm liền kề trong bộ nhớ → truy cập a[i] = O(1)

🔗 Danh sách liên kết đơn — Bộ nhớ rời rạc
10
→
head
25
→
7
→
42
→
NULL

Mỗi node chứa data + con trỏ next → phải duyệt tuần tự để đến phần tử i

📋 Bảng so sánh chi tiết

Thao tácArrayLinked List
Truy cập phần tử [i]O(1) ⚡O(n)
Chèn ở đầuO(n) — dịch cả mảngO(1) ⚡
Chèn ở cuốiO(1) amortizedO(n) — duyệt đến cuối
Xóa phần tửO(n) — dịchO(1) nếu có con trỏ
Tìm kiếmO(n) tuyến tínhO(n) tuyến tính
Bộ nhớLiên tục, ít overheadRời rạc, có overhead con trỏ
Cache-friendly✅ Rất tốt❌ Kém
📝 Kết luận

Array phù hợp khi cần truy cập ngẫu nhiên nhanh và dữ liệu ít thay đổi. Linked List phù hợp khi thường xuyên chèn/xóa ở đầu và không cần truy cập ngẫu nhiên.

← Trang chủ Chương 2: Sắp Xếp Cơ Bản →