Độ phức tạp (Big-O)

Mèo con cầm một cuốn danh bạ điện thoại đã xếp theo bảng chữ cái và cần tìm số của bạn “Miu”. Có hai cách. Cách thật thà: lật từng trang từ đầu cho tới khi gặp Miu. Cách khôn: mở ngay trang giữa, thấy tên ở đó đứng trước hay sau “Miu”, rồi chỉ tìm tiếp trong nửa còn lại - cứ thế chia đôi.

Với cuốn 1 000 trang, cách thật thà có thể phải lật tới 1 000 lần; cách khôn chỉ cần khoảng 10 lần chia đôi là ra. Phóng to lên 1 triệu trang: 1 000 000 lần so với khoảng 20 lần. Khoảng cách càng giãn ra khi danh bạ càng dày.

• ▸Cùng một việc “tìm một phần tử” có thể làm nhanh hay chậm tuỳ CÁCH làm.
• ▸Sự khác nhau lộ rõ khi dữ liệu lớn dần, không phải khi chỉ có vài phần tử.
• ▸Ta cần một thước đo “nhanh/chậm” không phụ thuộc máy mạnh hay yếu. Thước đó là Big-O.

Big-O mô tả số “thao tác cơ bản” một thuật toán phải làm tăng thế nào khi số phần tử n lớn dần. Nó không đo giây (máy khác nhau cho giây khác nhau) mà đo hình dạng tăng trưởng: n gấp đôi thì công việc tăng mấy lần?

Đếm rất trực giác: một vòng lặp quét hết mảng làm n phép - ta gọi là O(n). Hai vòng lồng nhau, mỗi vòng chạy hết mảng, làm khoảng n × n phép - đó là O(n²):

function demPhep(n: number) {
  let mot = 0, hai = 0;
  for (let i = 0; i < n; i++) mot++;        // 1 vong  -> n phep
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) hai++;       // 2 vong long -> n*n phep
  return { mot, hai };
}

console.log(demPhep(10));   // n = 10
console.log(demPhep(100));  // n = 100

{ mot: 10, hai: 100 }
{ mot: 100, hai: 10000 }

n tăng 10 lần (từ 10 lên 100) thì vòng đơn tăng đúng 10 lần (10 → 100), còn vòng lồng tăng tới 100 lần (100 → 10 000). Đó là khác biệt giữa O(n) và O(n²).

• ▸Big-O đếm thao tác cơ bản theo n, không đo thời gian tuyệt đối.
• ▸Một vòng lặp hết mảng = O(n); hai vòng lồng nhau = O(n²).
• ▸Quy ước: bỏ hằng số và số hạng nhỏ - vd 3n + 5 và 100n đều là O(n), vì khi n lớn, lớp tăng trưởng mới quyết định.

Hầu hết thuật toán rơi vào một trong sáu lớp quen mặt dưới đây, xếp từ rẻ tới đắt khi n lớn. Kéo thanh n trong bảng tương tác để xem mỗi lớp “ngốn” bao nhiêu phép tính, và nếu máy chạy 1 tỉ phép mỗi giây thì mất bao lâu:

Hãy để ý cột bên phải khi kéo n lên. Lớp O(2ⁿ) phình kinh khủng: mới n = 50 đã tốn khoảng 13 ngày, tới n = 100 thì lâu hơn cả tuổi vũ trụ. Trong khi đó O(log n) ở n = 1 triệu chỉ cần vỏn vẹn 20 phép.

• ▸O(1): không phụ thuộc n - vd lấy a[i] hay thêm vào cuối mảng.
• ▸O(log n): chia đôi mỗi bước - vd tìm nhị phân. O(n): quét cả mảng.
• ▸O(n log n): các thuật toán sắp xếp tốt. O(n²): hai vòng lồng. O(2ⁿ): thử mọi khả năng.

Quay lại cuốn danh bạ, lần này bằng code. Tìm tuyến tính quét lần lượt (O(n)); tìm nhị phân chia đôi mỗi bước (O(log n)). Ta cho cả hai cùng tìm số 999 trong mảng đã sắp [0, 1, …, 999] và đếm số phép so sánh:

function timTuyenTinh(a: number[], x: number) {
  let soPhep = 0;
  for (let i = 0; i < a.length; i++) {
    soPhep++;
    if (a[i] === x) return { index: i, soPhep };
  }
  return { index: -1, soPhep };
}

function timNhiPhan(a: number[], x: number) {
  let lo = 0, hi = a.length - 1, soPhep = 0;
  while (lo <= hi) {
    const giua = (lo + hi) >> 1;
    soPhep++;
    if (a[giua] === x) return { index: giua, soPhep };
    if (a[giua] < x) lo = giua + 1;  // x nam o nua ben phai
    else hi = giua - 1;              // x nam o nua ben trai
  }
  return { index: -1, soPhep };
}

const day = Array.from({ length: 1000 }, (_, i) => i); // [0, 1, ..., 999] da sap

console.log(timTuyenTinh(day, 999));
console.log(timNhiPhan(day, 999));

{ index: 999, soPhep: 1000 }
{ index: 999, soPhep: 10 }

Cùng cho ra đáp án index 999, nhưng tuyến tính tốn 1 000 phép so sánh còn nhị phân chỉ 10. Cái giá của tìm nhị phân: mảng phải được sắp xếp trước. Muốn vậy ta cần các thuật toán ở bài Sắp xếp & tìm kiếm; còn nếu muốn một cấu trúc luôn giữ thứ tự trong khi vẫn thêm/xoá được, đó là chuyện của Cây nhị phân tìm kiếm.

• ▸Tìm tuyến tính: O(n), chạy trên mọi mảng. Tìm nhị phân: O(log n), chỉ chạy trên mảng đã sắp.
• ▸Trên 1 000 phần tử: 1 000 phép so với 10 phép - khoảng cách càng giãn khi n lớn.
• ▸Nhị phân đáng công khi bạn tìm nhiều lần; sắp một lần rồi tìm mãi.

Vài điểm tinh tế giúp bạn đọc Big-O cho đúng. Một: Big-O bỏ hằng số, nên 2n và 100n đều là O(n). Nghe vô lý, nhưng khi n đủ lớn, một thuật toán O(n) “xấu” vẫn thắng một thuật toán O(n²) “đẹp”, vì đường thẳng rồi sẽ cắt dưới đường cong.

Hai: khi nói Big-O ta thường nói trường hợp xấu nhất - cái chặn trên chắc chắn. Tìm tuyến tính có thể may mắn gặp ngay phần tử đầu (1 phép), nhưng ta vẫn gọi nó O(n) vì lúc xui nhất phải quét hết. Ba: Big-O cũng dùng cho bộ nhớ (space complexity), không chỉ thời gian - tạo một bản sao của mảng tốn O(n) bộ nhớ.

• ▸Bỏ hằng số: 2n, 100n đều O(n) - lớp tăng trưởng mới quyết định khi n lớn.
• ▸Big-O thường chỉ trường hợp xấu nhất (chặn trên đảm bảo).
• ▸Có cả Big-O cho bộ nhớ, không riêng thời gian.

Giờ mèo con đã có la bàn chi phí: nhìn vào số vòng lặp lồng nhau là đoán được lớp Big-O; thuộc thứ tự sáu lớp từ O(1) tới O(2ⁿ); và biết rằng cùng một bài toán có thể giải nhanh hay chậm tuỳ cách làm. Đây là ngôn ngữ ta sẽ dùng để chấm điểm mọi cấu trúc và thuật toán trong cả khoá.