Độ phức tạp (Big-O)
- Độ khó
- ★★☆☆☆ Dễ
- Thời lượng
- Khoảng 75 phút
- Học trước
- Hàm tự tạo và đệ quy
- Chủ đề
- Big-Ođộ phức tạp
- Trạng thái
Kiến thức cơ bản
Khái niệm độ phức tạp thuật toán
Khi giải một bài toán lập trình, một lời giải không chỉ cần chạy đúng mà còn phải chạy đủ nhanh và tốn ít bộ nhớ. Để đánh giá một thuật toán nhanh hay chậm độc lập với tốc độ máy tính, ngôn ngữ lập trình hay hệ điều hành, các nhà khoa học máy tính sử dụng khái niệm Độ phức tạp thời gian (Time Complexity) và ký hiệu Big-O.
Big-O biểu thị số lượng phép toán cơ bản (phép cộng, trừ, nhân, chia, gán, so sánh) phụ thuộc vào kích thước dữ liệu đầu vào n. Hai quy tắc cơ bản khi xác định Big-O là:
- Bỏ hằng số: Thực hiện 3n hay 100n phép tính thì độ phức tạp vẫn là O(n).
- Quy tắc giữ lại bậc cao nhất: Nếu số phép tính là n² + 5n + 100, thì độ phức tạp vẫn gọi là O(n²).
Quy ước trong lập trình thi đấu
Trong lập trình thi đấu, mỗi bài có một giới hạn thời gian (thường là 1 giây). Máy tính thi đấu xử lý được khoảng 108 (100 triệu) phép tính cơ bản trong 1 giây. Vì vậy, nếu thuật toán >108 phép tính mặc dù cho kết quả đúng nhưng vẫn sẽ bị lỗi TLE (Time Limit Exceeded). Vì vậy, trước khi viết code ta cần ước lượng tốc độ của thuật toán.
Các phép toán cộng trừ nhân chia, rẽ nhánh if-else, truy xuất mảng qua chỉ số a[i] không phụ thuộc vào n, có độ phức tạp hằng số O(1).
Để biết chương trình chạy bao lâu, ta đếm xem lệnh bên trong vòng lặp được thực hiện bao nhiêu lần (gọi là biến đếm cnt).
// Ví dụ 1: một vòng lặp, cnt tăng n lần, O(n)
for (int i = 1; i <= n; ++i) cnt++;
// Ví dụ 2: hai vòng lặp lồng nhau, cnt tăng n.n = n2 lần, O(n2)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) cnt++;
// Ví dụ 3: hình tam giác, cnt tăng 1+2+...+n = n(n+1)/2 ~ n2 lần, O(n2)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j) cnt++;
// Ví dụ 4: chia đôi liên tục, cnt tăng khoảng log2(n) lần, O(logn)
for (int i = n; i >= 1; i /= 2) cnt++;
Bảng dưới đây cho biết số phép tính của các độ phức tạp thường gặp (ô xanh là kịp trong 1 giây, ô đỏ là quá chậm, theo quy ước 108 phép tính mỗi giây; log là logarit cơ số 2):
| n | O(logn) | O(√n) | O(n) | O(nlogn) | O(n²) | O(n³) | O(2n) |
|---|---|---|---|---|---|---|---|
| n = 10 | 3 | 3 | 10 | 33 | 100 | 1 000 | 1 024 |
| n = 100 | 7 | 10 | 100 | 664 | 10 000 | 106 | 1,3 × 1030 |
| n = 1 000 | 10 | 32 | 1 000 | 10 000 | 106 | 109 | rất lớn |
| n = 105 | 17 | 316 | 105 | 1,7 × 106 | 1010 | 1015 | rất lớn |
| n = 106 | 20 | 1 000 | 106 | 2 × 107 | 1012 | 1018 | rất lớn |
Chọn thuật toán dựa vào giới hạn của đề
Nhìn vào giới hạn của n trong đề bài, ta biết độ phức tạp tối đa có thể dùng. Hãy luôn đọc kỹ giới hạn trước khi nghĩ thuật toán:
| Giới hạn của n | Độ phức tạp có thể dùng | Ví dụ em đã gặp hoặc sắp gặp |
|---|---|---|
| n ≤ 10 | O(n!) | Thử mọi cách sắp xếp (quay lui, học ở giai đoạn sau) |
| n ≤ 20 | O(2n) | Chọn hoặc không chọn từng món quà (tuần 7) |
| n ≤ 300 | O(n³) | Ba vòng lặp lồng nhau |
| n ≤ 5 000 | O(n²) | Hai vòng lặp lồng nhau |
| n ≤ 106 | O(nlogn) hoặc O(n) | Mảng đếm, sàng nguyên tố, sắp xếp (học ở tuần sau) |
| n ≤ 1012 | O(√n) | Kiểm tra số nguyên tố, đếm ước |
| n ≤ 1018 | O(logn) | Lũy thừa nhanh, chia đôi liên tục, tìm kiếm nhị phân (tuần sau) |
Bộ nhớ
Ngoài thời gian, chương trình còn bị giới hạn bộ nhớ (thường khoảng 256 MB). Một số kiểu int chiếm 4 byte, kiểu long long chiếm 8 byte. Mảng 106 số int chiếm khoảng 4 MB, còn mảng 108 số int chiếm gần 400 MB, vượt quá giới hạn. Vì vậy khi dùng mảng đếm, em cần kiểm tra kích thước mảng trước.
Phân tích độ phức tạp của thuật toán
Mỗi câu dưới đây có đúng một đáp án đúng. Em hãy làm trên giấy nháp, không cần chạy chương trình. Quy ước: máy tính thực hiện 108 phép tính trong 1 giây; log là logarit cơ số 2; mỗi lệnh cnt++ là một phép tính; n là số nguyên dương lớn.
Đếm số phép tính và xác định độ phức tạp
Câu 1. Với n= 1000, lệnh cnt++ ở đoạn code sau được thực hiện bao nhiêu lần?
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) cnt++;
| A. 1 000 | B. 2 000 |
|---|---|
| C. 1 000 000 | D. 1 000 000 000 |
Câu 2. Với n= 100, lệnh cnt++ ở đoạn code sau được thực hiện bao nhiêu lần?
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j) cnt++;
| A. 100 | B. 5 050 |
|---|---|
| C. 10 000 | D. 10 100 |
Câu 3. Với n= 1024, lệnh cnt++ ở đoạn code sau được thực hiện bao nhiêu lần?
for (int i = n; i >= 1; i /= 2) cnt++;
| A. 10 | B. 512 |
|---|---|
| C. 1024 | D. 11 |
Câu 4. Hai vòng lặp chạy nối tiếp nhau (không lồng nhau), mỗi vòng lặp chạy n lần. Độ phức tạp của cả đoạn là:
| A. O(n²) | B. O(n) |
|---|---|
| C. O(logn) | D. O(n³) |
Câu 5. Số phép tính của một chương trình là 3n² + 5n + 20. Độ phức tạp của chương trình là:
| A. O(n) | B. O(3n²) |
|---|---|
| C. O(n³) | D. O(n²) |
Câu 6. Độ phức tạp của đoạn code sau là:
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= 100; ++j) cnt++;
| A. O(n) | B. O(n²) |
|---|---|
| C. O(100n²) | D. O(100) |
Câu 7. Độ phức tạp của đoạn code sau là:
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k) cnt++;
| A. O(n²) | B. O(3n) |
|---|---|
| C. O(n³) | D. O(nlogn) |
Câu 8. Độ phức tạp của đoạn code sau là:
for (int i = 1; i * i <= n; ++i) cnt++;
| A. O(n) | B. O(logn) |
|---|---|
| C. O(n²) | D. O(√n) |
Câu 9. Độ phức tạp của đoạn code sau là:
for (int i = 1; i <= n; i *= 3) cnt++;
| A. O(logn) | B. O(n/3) |
|---|---|
| C. O(√n) | D. O(n) |
Câu 10. Độ phức tạp của đoạn code sau là:
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; j *= 2) cnt++;
| A. O(n²) | B. O(nlogn) |
|---|---|
| C. O(n) | D. O(logn) |
Câu 11. Độ phức tạp của đoạn code sau là:
for (int i = 1; i <= n; ++i) cnt++;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) cnt++;
| A. O(n) | B. O(n³) |
|---|---|
| C. O(n²) | D. O(n + n²) |
Ước lượng chương trình có kịp 1 giây không
Câu 12. Một thuật toán có độ phức tạp O(n²), dữ liệu có n = 106. Chương trình có kịp 1 giây không?
A. Không kịp: cần khoảng 1012 phép tính
B. Kịp, vì n chỉ là một triệu
C. Kịp: cần khoảng 106 phép tính
D. Không kịp: cần khoảng 109 phép tính
Câu 13. Thuật toán có độ phức tạp O(nlogn), n = 105. Số phép tính ước lượng là:
| A. Khoảng 105, kịp | B. Khoảng 1010, không kịp |
|---|---|
| C. Khoảng 1,7 × 106, kịp | D. Khoảng 1015, không kịp |
Câu 14. Thuật toán có độ phức tạp O(n²), n = 5000. Chương trình có kịp 1 giây không?
A. Không, vì 5000 đã quá lớn
B. Không, vì cần khoảng 109 phép tính
C. Có, vì chỉ cần khoảng 5 000 phép tính
D. Có, vì cần khoảng 2,5 × 107 phép tính
Câu 15. Thuật toán có độ phức tạp O(n³), n = 1000. Nhận xét nào đúng?
A. Kịp: khoảng 3 000 phép tính
B. Không kịp: khoảng 109 phép tính, tức cỡ 10 giây
C. Kịp: khoảng 106 phép tính
D. Không kịp: khoảng 1012 phép tính
Câu 16. Thuật toán có độ phức tạp O(2n), n = 30. Nhận xét nào đúng?
| A. Không kịp: 230 ≈ 109 phép tính | B. Kịp, vì 30 là số nhỏ |
|---|---|
| C. Kịp: khoảng 900 phép tính | D. Kịp: 230 ≈ 106 phép tính |
Câu 17. Một chương trình O(n²) chạy mất 0,2 giây khi n = 104. Khi n tăng lên 105 (gấp 10 lần) thì thời gian chạy ước lượng là:
| A. 2 giây | B. 0,4 giây |
|---|---|
| C. 20 giây | D. 200 giây |
Câu 18. Một chương trình có độ phức tạp O(n), n = 109. Nhận xét nào đúng?
A. Không kịp theo quy ước: cần khoảng 109 phép tính, tức khoảng 10 giây
B. Chắc chắn kịp vì O(n) là độ phức tạp nhanh nhất
C. Kịp vì 109 nhỏ hơn 1018
D. Chỉ cần khoảng 103 phép tính nên kịp
Câu 19. Với n = 106, thuật toán có độ phức tạp nào dưới đây chắc chắn kịp 1 giây?
| A. O(n²) | B. O(n³) |
|---|---|
| C. O(2n) | D. O(nlogn) |
Chọn thuật toán theo giới hạn của đề
Câu 20. Với n ≤ 1012 và hỏi n có phải số nguyên tố không. Cách làm nào phù hợp?
| A. Thử mọi ước từ 2 đến n - 1 | B. Dùng sàng Eratosthenes đến n |
|---|---|
| C. Thử các ước từ 2 đến √n | D. Lập bảng mọi số nguyên tố < n |
Câu 21. Đề bài cho n ≤ 106 số, mỗi số a[i] ≤ 106, hỏi có hai số bằng nhau hay không. Cách làm nào nhanh và phù hợp?
A. So sánh từng cặp phần tử, O(n²)
B. Thử mọi tập con của dãy
C. Dùng đệ quy chia đôi dãy
D. Dùng mảng đếm kích thước 106 + 1, O(n)
Câu 22. Số cách chọn các tập con của n phần tử là bao nhiêu, và với n ≤ 20 em có thể duyệt hết không?
A. n² cách, khoảng 400, duyệt hết được
B. 2n cách, khoảng 106, duyệt hết được
C. n! cách, khoảng 2 × 1018, không duyệt hết được
D. 2n cách, khoảng 1018, không duyệt hết được
Câu 23. Để kiểm tra n có phải số nguyên tố, Nam dùng vòng lặp i từ 2 đến n - 1 thử chia. Với n = 109, chương trình của Nam chạy mất khoảng bao lâu (theo quy ước)?
| A. 0,01 giây | B. 10 giây |
|---|---|
| C. 1 giây | D. 3 giờ |
Câu 24. Để tính tổng 1 + 2 + ... + n với n = 109, cách nào nhanh nhất?
| A. Vòng lặp cộng từng số, O(n) | B. Hai vòng lặp lồng nhau, O(n²) |
|---|---|
| C. Đệ quy cộng từng số, O(n) | D. Dùng công thức n(n + 1)/2, O(1) |
Câu 25. Đề bài cho n ≤ 3000 và yêu cầu xét mọi cặp (i, j) với i < j. Có thể dùng hai vòng lặp lồng nhau không?
A. Được, vì cần khoảng 4,5 × 106 phép tính
B. Không, vì cần khoảng 109 phép tính
C. Không, vì O(n²) luôn quá chậm
D. Được, vì chỉ cần khoảng 3 000 phép tính
Luyện tập
Bài 1. Chia đôi liên tục
Với đoạn chương trình sau (cnt kiểu long long, ban đầu bằng 0), hãy cho biết giá trị cuối cùng của cnt. Lệnh i /= 2 chia i cho 2 và lấy phần nguyên.
for (long long i = n; i >= 1; i /= 2) cnt++;
| Đầu vào | Một số nguyên n (1 ≤ n ≤ 1018). | |
|---|---|---|
| Đầu ra | Giá trị của cnt sau khi chạy xong đoạn chương trình. | |
| Test | Input | Output |
| 8 | 4 | |
| 1000000000000000000 | 60 | |
Bài 2. Tổng từ 1 đến n
Bé Tí được giao tính tổng 1 + 2 + 3 + ... + n với n rất lớn. Nếu Tí cộng từng số một thì mất rất nhiều thời gian. Em hãy giúp Tí tìm cách tính nhanh nhé!
| Đầu vào | Một số nguyên n (1 ≤ n ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng 1 + 2 + ... + n. | |
| Test | Input | Output |
| 100 | 5050 | |
| 1000000000 | 500000000500000000 | |
Bài 3. Kiểm tra số nguyên tố (số lớn)
Cô giáo viết lên bảng một số n rất lớn và hỏi cả lớp: "Số này có phải số nguyên tố không?". Bạn hãy viết chương trình trả lời thật nhanh nhé!
| Đầu vào | Một số nguyên n (1 ≤ n ≤ 1012). | |
|---|---|---|
| Đầu ra | In YES nếu n là số nguyên tố, ngược lại in NO. | |
| Test | Input | Output |
| 999999999989 | YES | |
| 1000000000000 | NO | |
Bài 4. Đếm ước số thần tốc
Gấu được giao đếm số ước của những con số rất lớn. Là một người thạo lập trình, Gấu liền viết chương trình đếm số ước của n thật nhanh.
| Đầu vào | Một số nguyên n (1 ≤ n ≤ 1012). | |
|---|---|---|
| Đầu ra | Số lượng ước của n. | |
| Test | Input | Output |
| 36 | 9 | |
| 1000000000000 | 169 | |
Bài 5. Chạy kịp không?
Bạn Nam nghĩ ra một thuật toán và đã tính được độ phức tạp của nó. Hãy giúp Nam quyết định thuật toán đó có chạy kịp trong 1 giây hay không, theo quy ước máy tính thực hiện 108 phép tính trong 1 giây (số phép tính không vượt quá 108). Trong đó log lấy theo cơ số 2 và giữ nguyên giá trị thực (không làm tròn).
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 109). Dòng 2: kiểu độ phức tạp, là một trong các chuỗi: n, nlogn, n2, n3, 2^n (nlogn; n2 là n2; n3 là n3; 2^n là 2n). | |
|---|---|---|
| Đầu ra | In YES nếu số phép tính không vượt quá 108, ngược lại in NO. | |
| Test | Input | Output |
| 1000000 nlogn | YES | |
| 100000 n2 | NO | |
| 26 2^n | YES | |
Bài 6. Cặp số có tổng K
Cho dãy n số nguyên. Hãy đếm xem có bao nhiêu cặp chỉ số (i, j) với 0 ≤ i < j < n sao cho a[i] + a[j] = K.
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 2000; 1 ≤ K ≤ 2 × 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp thỏa mãn. | |
| Test | Input | Output |
| 5 7 1 6 2 5 7 | 2 | |
| 4 4 2 2 2 2 | 6 | |
Bài 7. Đoạn con có tổng lớn nhất
Một cửa hàng ghi lại lãi hoặc lỗ của n ngày liên tiếp (số âm là lỗ). Hãy chọn một khoảng gồm các ngày liên tiếp (ít nhất một ngày) sao cho tổng lãi của khoảng đó lớn nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 3000). Dòng 2: n số nguyên a[i] (│a[i]│ ≤ 106). | |
|---|---|---|
| Đầu ra | Tổng lớn nhất của một đoạn các phần tử liên tiếp. | |
| Test | Input | Output |
| 8 -2 1 -3 4 -1 2 1 -5 | 6 | |
| 3 -3 -1 -2 | -1 | |
Bài 8. Hai bạn trùng số áo
Lớp có n bạn, mỗi bạn mang một số áo. Hãy cho biết có hai bạn nào mang cùng một số áo hay không.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 106). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). | |
|---|---|---|
| Đầu ra | In YES nếu có hai bạn trùng số áo, ngược lại in NO. | |
| Test | Input | Output |
| 5 3 8 1 8 4 | YES | |
| 4 5 2 9 1 | NO | |
Bài tập tự luyện
Bài 1. Lồng nhau với chia đôi
Với đoạn chương trình sau (cnt kiểu long long, ban đầu bằng 0), hãy cho biết giá trị cuối cùng của cnt.
for (long long i = 1; i <= n; ++i)
for (long long j = 1; j <= n; j *= 2) cnt++;
| Đầu vào | Một số nguyên n (1 ≤ n ≤ 109). | |
|---|---|---|
| Đầu ra | Giá trị của cnt sau khi chạy xong đoạn chương trình. | |
| Test | Input | Output |
| 8 | 32 | |
| 1000 | 10000 | |
Bài 2. Cặp quân cờ giống nhau
Gấu Bo xếp một hàng gồm n quân cờ, mỗi quân ghi một số. Hãy đếm xem có bao nhiêu cặp chỉ số (i, j) với i < j mà hai quân cờ ở hai vị trí đó ghi cùng một số.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 106). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Số cặp quân cờ giống nhau. | |
| Test | Input | Output |
| 6 1 2 1 2 1 3 | 4 | |
| 4 5 5 5 5 | 6 | |
Bài 3. Hai số có tổng K (dữ liệu lớn)
Cho dãy n số nguyên dương. Hãy cho biết có tồn tại hai vị trí khác nhau i ≠ j sao cho a[i] + a[j] = K hay không.
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 106; 1 ≤ K ≤ 2 × 106). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). | |
|---|---|---|
| Đầu ra | In YES nếu tồn tại, ngược lại in NO. | |
| Test | Input | Output |
| 5 9 2 7 11 4 5 | YES | |
| 4 8 4 1 2 3 | NO | |
Bài 4. Số có nhiều ước nhất (giới hạn lớn)
Trong các số từ 1 đến n, hãy tìm số có nhiều ước dương nhất. Nếu có nhiều số cùng có số ước nhiều nhất thì chọn số nhỏ nhất. Lần này n lớn hơn nhiều so với bài ở tuần 7, nên cách đếm ước từng số sẽ không kịp thời gian.
| Đầu vào | Một số nguyên n (1 ≤ n ≤ 106). | |
|---|---|---|
| Đầu ra | Hai số cách nhau bởi dấu cách: số tìm được và số lượng ước của nó. | |
| Test | Input | Output |
| 100 | 60 12 | |
| 1000000 | 720720 240 | |
Bài 5. Số nguyên tố kế tiếp
Cho số n, hãy tìm số nguyên tố nhỏ nhất lớn hơn n.
| Đầu vào | Một số nguyên n (1 ≤ n ≤ 1012). | |
|---|---|---|
| Đầu ra | Số nguyên tố nhỏ nhất lớn hơn n. | |
| Test | Input | Output |
| 100 | 101 | |
| 1000000000000 | 1000000000039 | |
Bài 6. Dãy con có tổng K
Cho dãy n số nguyên dương. Hãy đếm xem có bao nhiêu đoạn gồm các phần tử liên tiếp có tổng đúng bằng K.
| Đầu vào | Dòng 1: hai số nguyên n, K (1 ≤ n ≤ 5000; 1 ≤ K ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Số đoạn con liên tiếp có tổng bằng K. | |
| Test | Input | Output |
| 5 5 1 2 3 2 3 | 3 | |
| 4 3 1 1 1 1 | 2 | |
Bài 7. Ba số có tổng K
Cho dãy n số nguyên dương. Hãy đếm xem có bao nhiêu bộ ba chỉ số (i, j, k) với i < j < k sao cho a[i] + a[j] + a[k] = K.
| Đầu vào | Dòng 1: hai số nguyên n, K (3 ≤ n ≤ 300; 1 ≤ K ≤ 3 × 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số bộ ba thỏa mãn. | |
| Test | Input | Output |
| 5 10 1 2 3 4 5 | 2 | |
| 4 6 2 2 2 2 | 4 | |
Bài 8. Thử thách: Tổng đoạn nhiều câu hỏi
Cho dãy n số và q câu hỏi, mỗi câu hỏi gồm hai số l, r, yêu cầu tính tổng các phần tử từ vị trí l đến vị trí r (vị trí đếm từ 1). Nếu với mỗi câu hỏi em cộng từng số thì mất khoảng n × q phép tính, quá chậm. Em hãy tìm cách làm nhanh hơn! (Bài này mở đường cho kỹ thuật mảng cộng dồn em sẽ học ở các tuần sau.)
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 104). q dòng tiếp theo, mỗi dòng gồm hai số l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là tổng của một câu hỏi. | |
| Test | Input | Output |
| 5 3 1 2 3 4 5 1 3 2 5 4 4 | 6 14 4 | |