Độ phức tạp thuật toán đo số bước một thuật toán cần làm theo kích thước đầu vào n, và ký hiệu Big O mô tả số bước đó tăng nhanh cỡ nào khi n lớn, bỏ qua hằng số và các số hạng nhỏ. Nói thuật toán chạy trong O(n bình phương) nghĩa là khi n tăng gấp đôi, số bước ở trường hợp xấu nhất tăng khoảng gấp bốn; O(log n) nghĩa là n tăng gấp đôi thì chỉ thêm khoảng một bước.
Nhiều người học Big O như một bảng tra: vòng lặp đơn là n, hai vòng lồng là n bình phương. Bảng tra đó đúng phần lớn thời gian và sai đúng ở những chỗ quan trọng. Bài giải thích Big O bằng phép đếm, đưa định nghĩa chính xác kèm một ví dụ chứng minh, bảng so sánh tốc độ tăng, các ví dụ kinh điển, và những lỗi phân tích mà cả người lẫn AI hay mắc.
Đếm bước: vì sao không đo bằng giây
Thời gian chạy thật phụ thuộc máy, ngôn ngữ, trình biên dịch, và việc máy đang bận gì khác. Để so sánh hai thuật toán công bằng, người ta đếm số phép toán cơ bản, như so sánh hai số, cộng, gán, truy cập một ô nhớ, như một hàm của kích thước đầu vào n. Số đếm này không đổi khi bạn chuyển sang máy nhanh hơn; chỉ có thời gian của một bước tính bằng giây thay đổi.
Ví dụ: tìm một số trong danh sách n số chưa sắp xếp bằng cách xét lần lượt từng phần tử. Trường hợp xấu nhất, số cần tìm ở cuối hoặc không có, cần n lần so sánh. Trường hợp tốt nhất là một lần. Trung bình, nếu số cần tìm có mặt và vị trí của nó ngẫu nhiên đều, cần khoảng (n + 1)/2 lần. Phân tích độ phức tạp thường nói về trường hợp xấu nhất, vì đó là lời bảo đảm: thuật toán không bao giờ chậm hơn mức này.
Câu hỏi tiếp theo là có cần đếm chính xác không. Thường là không. Một thuật toán cần 3n + 5 bước và một thuật toán cần 7n bước khác nhau một hằng số, và hằng số đó có thể đảo chiều khi đổi máy hay đổi ngôn ngữ. Điều không đổi là cả hai đều tăng tuyến tính theo n. Big O ra đời để giữ lại đúng thông tin bền vững đó và bỏ phần còn lại.
Định nghĩa chính xác và một ví dụ chứng minh
Định nghĩa: f(n) = O(g(n)) nếu tồn tại hằng số dương c và số n0 sao cho f(n) ≤ c nhân g(n) với mọi n ≥ n0. Nói bằng lời: từ một ngưỡng nào đó trở đi, f không vượt quá một bội cố định của g. Big O vì vậy là một cận trên, không phải đẳng thức. Viết n = O(n bình phương) là đúng, chỉ là một cận lỏng.
Ví dụ chứng minh 3n bình phương + 5n + 2 = O(n bình phương). Chọn c = 4, cần 3n bình phương + 5n + 2 ≤ 4n bình phương, tức n bình phương − 5n − 2 ≥ 0. Phương trình n bình phương − 5n − 2 = 0 có nghiệm dương khoảng 5,37, nên bất đẳng thức đúng với mọi n ≥ 6. Chọn n0 = 6 là xong. Kiểm nhanh tại n = 6: vế trái 108 + 30 + 2 = 140, vế phải 144. Đúng. Cũng có thể chọn c = 10 và n0 = 1, vì với n ≥ 1 thì 5n ≤ 5n bình phương và 2 ≤ 2n bình phương; cặp c, n0 không duy nhất.
Hai ký hiệu đi kèm thường gặp: Ω (omega lớn) là cận dưới, f(n) ≥ c nhân g(n) từ một ngưỡng nào đó; Θ (theta lớn) là vừa cận trên vừa cận dưới, tức f tăng đúng cỡ g. Trong giao tiếp hằng ngày, lập trình viên hay nói “O(n bình phương)” khi thật ra muốn nói Θ. Trong bài thi toán rời rạc, phân biệt ba ký hiệu này là chỗ hay bị trừ điểm.
Bảng tốc độ tăng: con số nói thay lời giải thích
Bảng dưới ghi số bước xấp xỉ của các lớp độ phức tạp thường gặp tại ba kích thước đầu vào. Logarit lấy cơ số 2, số đã làm tròn.
| Lớp | n = 10 | n = 1.000 | n = 1.000.000 | Ví dụ |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | Lấy phần tử thứ i của mảng |
| O(log n) | khoảng 3 | khoảng 10 | khoảng 20 | Tìm kiếm nhị phân |
| O(n) | 10 | 1.000 | 1.000.000 | Duyệt danh sách một lần |
| O(n log n) | khoảng 33 | khoảng 10.000 | khoảng 20 triệu | Sắp xếp trộn |
| O(n bình phương) | 100 | 1 triệu | 1.000 tỷ | So mọi cặp phần tử |
| O(2 mũ n) | 1.024 | số có hơn 300 chữ số | không còn ý nghĩa thực tế | Duyệt mọi tập con |
Giả sử máy làm được khoảng một tỷ bước mỗi giây, một mức xấp xỉ để minh hoạ. Với một triệu phần tử, thuật toán n log n xong trong vài phần trăm giây, còn thuật toán n bình phương cần khoảng 1.000 giây, gần 17 phút. Không có tối ưu hằng số nào bù được khoảng cách đó; chỉ đổi sang lớp thuật toán khác mới bù được. Đó là lý do người ta học Big O.
Dòng cuối cũng giải thích vì sao bài toán duyệt mọi tập con, như thử mọi tổ hợp món hàng để tối ưu một giỏ hàng, chỉ làm được với vài chục phần tử. Gặp bài toán có số khả năng tăng theo hàm mũ, câu hỏi đúng không phải “máy nhanh cỡ nào” mà là “có cách nào tránh duyệt hết không”.
Ba ví dụ kinh điển, phân tích từng bước
Ba ví dụ dưới đây gần như có mặt trong mọi giáo trình. Chú ý cách đếm, không chỉ kết quả.
- Tìm kiếm nhị phân trên dãy đã sắp xếp. Mỗi lần so với phần tử giữa, nửa không chứa đáp án bị loại. Sau k lần so, phạm vi còn khoảng n chia 2 mũ k phần tử. Dừng khi còn một phần tử, tức 2 mũ k khoảng bằng n, nên k khoảng log n. Với một triệu phần tử, nhiều nhất 20 lần so, vì 2 mũ 20 = 1.048.576 đã vượt một triệu. So với tìm tuần tự cần tới một triệu lần, chênh lệch là năm vạn lần.
- Hai vòng lặp lồng xét mọi cặp. Kiểm danh sách có hai phần tử trùng nhau bằng cách so mọi cặp vị trí i đứng trước j. Số cặp là n(n − 1)/2; với n = 1.000 là 499.500 cặp. Hằng số 1/2 bị bỏ, kết quả là Θ(n bình phương).
- Sắp xếp nổi bọt và sắp xếp trộn. Nổi bọt so và đổi chỗ các cặp kề nhau qua nhiều lượt, trường hợp xấu nhất cỡ n bình phương phép so sánh. Trộn chia đôi dãy, sắp từng nửa rồi trộn, thoả hệ thức T(n) = 2T(n/2) + cn, cho Θ(n log n). Có thể chứng minh mọi thuật toán sắp xếp chỉ dựa vào so sánh đều cần cỡ n log n phép so sánh ở trường hợp xấu nhất, nên sắp xếp trộn đã tối ưu theo nghĩa đó.
Bài toán ở ví dụ thứ hai có cách làm tốt hơn: sắp xếp trước rồi chỉ so các phần tử kề nhau, tổng cỡ n log n; hoặc dùng bảng băm, trung bình cỡ n. Cùng một bài toán, ba lớp độ phức tạp. Đây là kiểu cải tiến mà phân tích Big O giúp bạn nhìn ra trước khi viết dòng mã nào.
Những lỗi phân tích mà cả người lẫn AI hay mắc
Đếm vòng lặp mà quên chi phí bên trong. Một vòng lặp chạy n lần, mỗi lần kiểm “phần tử này có trong danh sách kia không” bằng phép tìm tuần tự, thực chất là n nhân n. Câu lệnh trông chỉ một dòng nhưng tốn n bước. Chatbot hay đọc lướt và kết luận O(n) cho đoạn mã kiểu này.
Coi mọi vòng lặp lồng là n bình phương. Vòng ngoài chạy n lần, vòng trong mỗi lần chia đôi biến đếm thì tổng chỉ cỡ n log n. Phải đếm số lần vòng trong thật sự chạy.
Lẫn trường hợp xấu nhất với trung bình. Sắp xếp nhanh trung bình cỡ n log n nhưng xấu nhất cỡ n bình phương. Bảng băm trung bình là hằng số nhưng xấu nhất là tuyến tính. Nói độ phức tạp mà không nói trường hợp nào là chưa đủ.
Bỏ qua kích thước của chính các con số. Cộng hai số được coi là một bước khi số vừa một ô nhớ. Với số nguyên rất lớn, như trong mật mã, phép cộng và phép nhân tốn thời gian tăng theo số chữ số; phân tích phải đổi đơn vị đo.
Tin rằng hằng số không bao giờ quan trọng. Với n nhỏ, thuật toán n bình phương có hằng số nhỏ có thể nhanh hơn thuật toán n log n có hằng số lớn. Nhiều thư viện sắp xếp chuyển sang sắp xếp chèn khi đoạn cần sắp đủ ngắn vì lý do này.
Nhầm độ phức tạp với thời gian đo được. Big O nói về xu hướng khi n lớn. Muốn biết chương trình cụ thể chạy bao lâu, phải đo; muốn biết nó có chịu được dữ liệu gấp mười lần không, phân tích Big O trả lời tốt hơn.
Dùng AI để luyện phân tích độ phức tạp
Phân tích độ phức tạp là kỹ năng đếm, và AI hợp làm người ra đề và người phản biện hơn là người giải hộ. Quy trình gợi ý:
- Nhờ AI sinh các đoạn mã giả ngắn có vòng lặp với độ khó tăng dần: vòng đơn, vòng lồng, vòng chia đôi, đệ quy. Yêu cầu nó chưa nói đáp án.
- Tự phân tích, viết rõ mỗi vòng chạy bao nhiêu lần và tổng số bước dưới dạng biểu thức trước khi rút về Big O.
- Gửi bài kèm câu lệnh mẫu: “Đây là cách mình đếm số bước cho đoạn mã này. Kiểm từng bước đếm, đặc biệt các phép toán bên trong vòng lặp có chi phí ẩn. Chỉ ra chỗ sai, đừng viết lời giải mới.”
- Kiểm bằng thực nghiệm: cài đoạn mã, chạy với n bằng 1.000, 2.000, 4.000 và ghi thời gian. Nếu thời gian gấp đôi theo n, nghĩ tới tuyến tính; gấp bốn, nghĩ tới bình phương. Thực nghiệm không thay chứng minh nhưng bắt được phân tích sai rất nhanh.
- Khi AI và bạn cho hai kết quả khác nhau, yêu cầu nó đếm cụ thể số lần lặp với n = 8 hoặc n = 16. Đếm trên số nhỏ cụ thể là cách nhanh nhất để thấy bên nào đúng.
Nếu bạn mang mã nguồn công ty ra hỏi, chỉ dán đoạn thuật toán đã bỏ tên biến nghiệp vụ, khoá truy cập và dữ liệu thật; phân tích độ phức tạp không cần những thứ đó.
Câu hỏi thường gặp
O(log n) dùng logarit cơ số mấy?
Không quan trọng trong ký hiệu Big O, vì logarit các cơ số khác nhau chỉ chênh nhau một hằng số nhân: log cơ số 2 của n bằng log cơ số 10 của n nhân khoảng 3,32. Hằng số bị Big O bỏ qua. Trong khoa học máy tính, khi cần con số cụ thể, người ta thường ngầm hiểu cơ số 2.
Độ phức tạp bộ nhớ là gì?
Là lượng bộ nhớ thêm mà thuật toán cần, cũng viết bằng Big O theo n. Sắp xếp trộn cần thêm bộ nhớ cỡ n để trộn, trong khi một số thuật toán sắp xếp tại chỗ chỉ cần thêm một lượng hằng số. Thời gian và bộ nhớ thường đổi chác cho nhau: lưu sẵn kết quả để tính nhanh hơn là một ví dụ.
P và NP liên quan gì tới Big O?
Lớp P gồm các bài toán giải được trong thời gian đa thức, tức O(n mũ k) với k cố định. Lớp NP gồm các bài toán mà một lời giải được đưa ra có thể kiểm tra trong thời gian đa thức. Câu hỏi P có bằng NP không là một trong các bài toán thiên niên kỷ của Viện Toán học Clay, đến nay chưa có lời giải.
Có cần học Big O nếu chỉ dùng thư viện có sẵn?
Có, ở mức đủ dùng. Thư viện cho bạn các thao tác nhanh, nhưng ghép chúng sai cách vẫn ra chương trình chậm, ví dụ gọi tìm kiếm tuần tự bên trong vòng lặp. Biết độ phức tạp của các thao tác cơ bản trên danh sách, tập hợp, từ điển là đủ để tránh phần lớn lỗi hiệu năng hay gặp.
Thuật toán O(n) có luôn nhanh hơn O(n bình phương) không?
Không luôn luôn. Big O chỉ khẳng định điều đó khi n đủ lớn. Với n nhỏ, hằng số và chi phí phụ có thể làm thuật toán bình phương chạy nhanh hơn. Ngoài ra Big O thường nói về trường hợp xấu nhất, trong khi dữ liệu thật có thể luôn rơi vào trường hợp thuận lợi.