Elearning CodePath – CTP Online Judge

🎯 Mục tiêu bài học

Biết ước lượng thuật toán có chạy kịp hay không trong giới hạn đề.
Biết vì sao cần tối ưu từ O(n³) → O(n²) → O(n log n).
Hiểu mối quan hệ giữa thời gian chạy và bộ nhớ.

📘 1️⃣ Vì sao phải quan tâm đến độ phức tạp?

Trong đề thi lập trình, input có thể rất lớn (ví dụ n = 200 000). Nếu em viết thuật toán O(n²), thì với n = 200 000:

n² = 200 000 × 200 000 = 40 000 000 000 (40 tỷ vòng lặp) ⟶ không thể chạy kịp.

Kinh nghiệm thi: ~10⁸ phép toán trong 1s bằng C++ là ngưỡng thô thường dùng để ước lượng. Python thì chậm hơn nhiều, nên với Python phải cố gắng O(n log n) hoặc O(n).

📘 2️⃣ Ví dụ tối ưu hoá: tính tổng mọi subarray

Bài toán: Cho mảng a[0..n-1], tính tổng của tất cả các đoạn con (subarray).

❌ Cách chậm O(n³)

// C++
long long brute_force_sum(const vector& a){
    long long ans=0;
    for(int i=0;i



✅ Cải tiến O(n²) với prefix sum
// C++
long long prefix_sum_optimized(const vector& a){
    int n=a.size();
    vector pref(n+1,0);
    for(int i=0;i


Ta thay vòng lặp trong cùng (O(n)) bằng truy vấn tổng đoạn O(1).



📗 3️⃣ Bộ nhớ cũng là rào cản

Nếu em tạo mảng 2D kích thước 5000 × 5000 số nguyên 64-bit:


5000 × 5000 = 25 000 000 phần tử  
25 triệu × 8 byte ≈ 200 MB → có thể vượt limit bộ nhớ đề (thường 64MB / 256MB).



Tức là: không chỉ thời gian, mà cả RAM cũng có giới hạn thi.




🧩 Bài tập luyện tập

  Với n = 10⁵, thuật toán O(n²) có chạy được không? Giải thích.
  Viết lại một thuật toán chậm em từng làm (ví dụ đếm tần suất ký tự bằng vòng lặp lồng) thành phiên bản O(n).
  Xác định độ phức tạp đoạn code em vừa nộp hôm qua (thói quen tự đánh giá trước khi submit).



  💡 Gợi ý câu 1
  n = 100000
n^2 = 10^10 = mười tỷ bước → quá lớn trừ khi có trick đặc biệt / pruning.