Độ phức tạp thuật toán và ký hiệu O (O-Notation)

1. Tổng quan

A. Định nghĩa

Độ phức tạp thuật toán (complexity) là lượng tài nguyên mà thuật toán tiêu tốn theo kích thước đầu vào (n), được chia thành độ phức tạp thời gian đo số phép tính và độ phức tạp không gian đo bộ nhớ. Ký hiệu O (Big-O) là cách biểu diễn tốc độ tăng (cận trên tiệm cận, asymptotic upper bound) khi đầu vào trở nên đủ lớn.

Lý do đo độ phức tạp bằng tốc độ tăng của số phép tính chứ không phải thời gian chạy thực tế (giây) là điều quan trọng. Thời gian chạy thay đổi theo hiệu năng CPU, ngôn ngữ, trình biên dịch nên không thể đánh giá hơn kém của bản thân thuật toán, còn "khi đầu vào tăng gấp 2 thì số phép tính tăng bao nhiêu lần" là tính chất cố hữu của thuật toán không phụ thuộc phần cứng. Vì vậy ký hiệu O bỏ các hằng số và số hạng bậc thấp, chỉ giữ lại tốc độ tăng của số hạng chi phối nhất — ví dụ 3n²+5n+7 khi n lớn thì số hạng n² chi phối nên được ký hiệu là O(n²).

B. Các loại ký hiệu tiệm cận

Không chỉ có một ký hiệu O, mà có ba ký hiệu lần lượt biểu diễn cận trên, cận dưới và cận chính xác. Trong thực tế, bảo đảm trường hợp xấu nhất là quan trọng về mặt an toàn thiết kế nên ký hiệu O biểu diễn cận trên được dùng rộng rãi nhất.

2. Các dạng ký hiệu O và khối lượng tính toán

Biểu đồ dưới đây cho thấy khối lượng tính toán của từng độ phức tạp chênh lệch thế nào khi kích thước đầu vào n tăng. Khi n nhỏ, khác biệt không đáng kể, nhưng khi n lớn thì từ O(n²) trở lên phân kỳ nhanh chóng và gần như không thể thực thi. Chính khác biệt ở n lớn này quyết định việc chọn thuật toán.

{
  "type": "line",
  "data": {
    "labels": ["1","2","4","8","16","32","64"],
    "datasets": [
      { "label": "O(1)", "data": [1,1,1,1,1,1,1], "borderColor": "#0e9f6e", "tension": 0.2 },
      { "label": "O(log n)", "data": [0,1,2,3,4,5,6], "borderColor": "#2f6fed", "tension": 0.2 },
      { "label": "O(n)", "data": [1,2,4,8,16,32,64], "borderColor": "#f59e0b", "tension": 0.2 },
      { "label": "O(n log n)", "data": [0,2,8,24,64,160,384], "borderColor": "#8b5cf6", "tension": 0.2 },
      { "label": "O(n^2)", "data": [1,4,16,64,256,1024,4096], "borderColor": "#e11d48", "tension": 0.2 }
    ]
  },
  "options": {
    "plugins": { "legend": { "position": "bottom" }, "title": { "display": true, "text": "Mức tăng số phép tính theo kích thước đầu vào (n)" } },
    "scales": { "y": { "title": { "display": true, "text": "Số phép tính" } } }
  }
}

Mỗi dạng bắt nguồn từ cấu trúc hoạt động của thuật toán. Hiểu vì sao có độ phức tạp đó thì chỉ nhìn mã cũng có thể ước lượng độ phức tạp.

• O(1) hằng số: Số phép tính cố định bất kể kích thước đầu vào. Là trường hợp tính vị trí trong một lần như tra cứu băm, truy cập chỉ số mảng.
• O(log n) logarit: Cấu trúc mỗi bước thu hẹp phạm vi tìm kiếm còn một nửa. Tìm kiếm nhị phân là tiêu biểu, dù n là một triệu cũng chỉ khoảng 20 lần là xong.
• O(n) tuyến tính: Cấu trúc duyệt qua đầu vào một lần. Tìm kiếm tuần tự, tính tổng là như vậy.
• O(n log n) tuyến tính-logarit: Cấu trúc chia dữ liệu (log n bước) rồi ở mỗi bước duyệt toàn bộ (n). Là cận dưới của sắp xếp hiệu quả như sắp xếp trộn, sắp xếp nhanh.
• O(n²) bình phương: Cấu trúc so sánh mọi cặp bằng vòng lặp lồng nhau. Sắp xếp nổi bọt, sắp xếp chèn thuộc dạng này, và chậm đi nhanh chóng khi n lớn.
• O(2ⁿ) mũ: Cấu trúc mỗi bước số trường hợp phân nhánh gấp 2. Fibonacci đệ quy không có ghi nhớ (memoization), liệt kê tập con là như vậy.
• O(n!) giai thừa: Cấu trúc thử mọi hoán vị. Tìm kiếm vét cạn bài toán người bán hàng (TSP) là tiêu biểu, chỉ cần n=20 là không thể tính được.

Tốc độ tăng: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

3. Phân tích theo trường hợp

Cùng một thuật toán nhưng hiệu năng thay đổi theo trạng thái của đầu vào, nên phân tích phân biệt tốt nhất, trung bình, xấu nhất. Ví dụ, sắp xếp nhanh nếu mỗi lần chọn pivot gần trung vị thì trung bình O(n log n), nhưng với mảng đã sắp xếp mà chọn pivot sai thì phân chia lệch về một phía và thành xấu nhất O(n²). Trong thiết kế, thông thường phải lấy trường hợp xấu nhất (O) làm chuẩn thì mới bảo đảm hiệu năng trong dịch vụ thực tế.

4. Lưu ý và hàm ý

• Với n lớn, độ phức tạp chi phối hiệu năng: Với dữ liệu quy mô nhỏ, khác biệt hằng số lớn nên O(n²) có thể nhanh hơn O(n log n), nhưng với dung lượng lớn thì độ phức tạp tiệm cận là tuyệt đối. Mấu chốt là chọn thuật toán phù hợp với quy mô dữ liệu.
• Đánh đổi thời gian và không gian: Độ phức tạp được hoán đổi giữa thời gian và không gian. Chẳng hạn, caching, memoization dùng thêm bộ nhớ (không gian) để giảm tính toán lặp lại (thời gian) — việc ghi nhớ Fibonacci đệ quy giảm O(2ⁿ) xuống O(n) là tình huống tiêu biểu.
• Bổ khuyết giới hạn của phân tích tiệm cận: Vì hằng số, phần cứng, tính cục bộ cache, hệ số hằng bị bỏ qua, khi tinh chỉnh thực tế cần song song đo đạc thực bằng profiling.
• Liên kết và triển vọng: Việc có giải được trong thời gian đa thức (P) hay không là chủ đề cốt lõi của lý thuyết độ phức tạp tính toán như P-NP, và các bài toán NP-khó có độ phức tạp O(n!) như TSP tìm lời giải thực tế bằng xấp xỉ, heuristic, quy hoạch động. Phân tích độ phức tạp là thước đo cơ bản của lựa chọn và tối ưu hóa thuật toán.

Tóm tắt một câu: Ký hiệu O biểu diễn tốc độ tăng xấu nhất (cận trên tiệm cận) của thuật toán theo kích thước đầu vào một cách độc lập với phần cứng; hiệu năng xấu đi nhanh chóng theo thứ tự O(1)→O(log n)→O(n)→O(n log n)→O(n²)→O(2ⁿ)→O(n!), và thuật toán được lựa chọn có xét đến đánh đổi thời gian-không gian và tính chi phối khi n lớn.