Cấu trúc dữ liệu và Giải thuật Bài 3: Độ phức tạp thời gian (Time Complexity) và Ký pháp Big-O.

Khi bạn viết một đoạn code và chạy thử với 10 bản ghi, nó hoàn thành trong 0.01 giây. Bạn cho rằng thuật toán của mình đã đủ nhanh. Nhưng khi triển khai lên production, với 1 triệu bản ghi, đoạn code đó không mất 1 giây, mà mất đến... 2.7 tiếng đồng hồ để chạy xong.

Tại sao lại có sự phi lý này? Đó là bởi vì thời gian thực thi (execution time) được đo bằng giây không phải là thước đo chuẩn xác để đánh giá một thuật toán. Để dự đoán được hệ thống sẽ phản ứng thế nào khi dữ liệu bùng nổ, chúng ta cần một ngôn ngữ chung: Ký pháp Big-O (Big-O Notation).

1. Tại sao không dùng "Giây" để đo tốc độ thuật toán?

Thời gian chạy thực tế của một chương trình phụ thuộc vào quá nhiều yếu tố phần cứng vật lý:

• Bạn chạy code trên một vi điều khiển ESP32 sẽ chậm hơn rất nhiều so với chạy trên một server AWS EC2.

• Code chạy lúc CPU đang rảnh rỗi sẽ nhanh hơn lúc hệ điều hành đang phải xử lý hàng trăm tiến trình ngầm khác.

• Trình biên dịch (Compiler) của C++ (GCC) có thể tối ưu code tốt hơn trình thông dịch của PHP hoặc Node.js.

Do đó, các kỹ sư phần mềm không đo "thời gian" bằng giây. Chúng ta đo số lượng phép toán (operations) mà thuật toán cần thực hiện, và quan trọng nhất là sự tăng trưởng của số lượng phép toán đó khi kích thước dữ liệu đầu vào ($n$) tăng lên.

2. Ký pháp Big-O là gì?

Big-O Notation là một ngôn ngữ toán học dùng để mô tả trường hợp xấu nhất (worst-case scenario) của một thuật toán. Nó trả lời cho câu hỏi: "Khi dữ liệu đầu vào tiến tới vô cùng, thời gian chạy của thuật toán sẽ tăng theo cấp độ nào?"

Hãy cùng đi qua các "đẳng cấp" của Big-O từ nhanh nhất đến chậm nhất:

$O(1)$ - Constant Time (Thời gian hằng số)

Đây là "chén thánh" của tối ưu hóa. Bất kể dữ liệu đầu vào là 10 phần tử hay 10 tỷ phần tử, số bước thực hiện luôn cố định.

• Ví dụ: Truy cập phần tử mảng bằng index (arr[5]), lấy giá trị từ Hash Map ($map['key']), kiểm tra số chẵn lẻ.

• Tư duy: Hệ thống có scale cỡ nào, logic của bạn vẫn chạy tức thì.

$O(\log n)$ - Logarithmic Time (Thời gian logarit)

Cực kỳ hiệu quả đối với tập dữ liệu lớn. Đặc điểm của thuật toán này là sau mỗi bước, nó loại bỏ đi một nửa số lượng dữ liệu cần xử lý.

• Ví dụ: Tìm kiếm nhị phân (Binary Search), thao tác trên cây nhị phân cân bằng (AVL, Red-Black Tree).

• Sức mạnh: Với $n = 1,000,000$, $O(n)$ cần 1 triệu phép thử, nhưng $O(\log n)$ chỉ cần tối đa 20 phép thử. Nếu $n$ tăng lên 1 tỷ, nó cũng chỉ tốn thêm 10 bước (tổng cộng 30 phép thử).

$O(n)$ - Linear Time (Thời gian tuyến tính)

Dữ liệu tăng bao nhiêu, thời gian chạy tăng bấy nhiêu. Đồ thị của nó là một đường chéo đi lên.

• Ví dụ: Dùng vòng lặp for hoặc foreach duyệt qua toàn bộ mảng; tìm giá trị lớn nhất trong mảng chưa sắp xếp.

• Tư duy: Chấp nhận được, nhưng nếu $n$ lên tới hàng triệu, bắt đầu xuất hiện độ trễ (latency).

$O(n \log n)$ - Linearithmic Time

Độ phức tạp tiêu chuẩn cho các thuật toán sắp xếp (sorting) tối ưu nhất hiện nay.

• Ví dụ: Merge Sort, Quick Sort, Heap Sort.

• Tư duy: Nhanh hơn nhiều so với việc lặp lồng nhau, là giới hạn tối đa để sắp xếp dữ liệu có quy mô lớn.

$O(n^2)$ - Quadratic Time (Thời gian bậc hai)

Đây là "bẫy" mà các lập trình viên thường mắc phải khi sử dụng 2 vòng lặp lồng nhau.

• Ví dụ: Duyệt mảng 2 chiều, thuật toán sắp xếp nổi bọt (Bubble Sort), kiểm tra tất cả các cặp phần tử (bài toán 2Sum dùng Brute Force).

• Hiểm họa: Nếu $n = 100$, mất 10,000 bước. Nhưng nếu $n = 10,000$, nó nhảy vọt lên 100 triệu bước. Hệ thống sẽ quá tải ngay lập tức nếu không áp dụng phân trang (Pagination) hoặc Batching.

$O(2^n)$ và $O(n!)$ - Exponential / Factorial Time (Thời gian hàm mũ / Giai thừa)

Cơn ác mộng của khoa học máy tính. Chỉ cần $n$ tăng thêm 1 đơn vị, khối lượng tính toán sẽ tăng gấp đôi (hoặc gấp nhiều lần).

• Ví dụ: Thuật toán tính dãy Fibonacci bằng đệ quy không nhớ (naive recursion), bài toán người bán hàng (Travelling Salesman Problem).

• Tư duy: Không bao giờ sử dụng trong thực tế với $n > 30$. Bắt buộc phải dùng Quy hoạch động (Dynamic Programming) hoặc các kỹ thuật cắt tỉa (Pruning) để tối ưu.

3. Các quy tắc "vàng" khi tính toán Big-O

Khi đánh giá một thuật toán, chúng ta không đếm chi li từng dòng code. Big-O tập trung vào bức tranh toàn cảnh, do đó bạn cần nắm vững hai quy tắc loại trừ sau:

Quy tắc 1: Lờ đi các hằng số (Drop Constants)

Giả sử bạn có một đoạn code gồm 2 vòng lặp for chạy tuần tự (không lồng nhau). Vòng lặp 1 duyệt $n$ phần tử, vòng lặp 2 cũng duyệt $n$ phần tử. Tổng số phép toán là $2n$.

Theo quy tắc Big-O, $O(2n)$ hay $O(100n)$ đều được rút gọn thành $O(n)$. Bởi vì khi $n$ tiến tới vô cùng, hằng số phía trước không làm thay đổi bản chất của đường cong tăng trưởng.

Quy tắc 2: Lờ đi các hạng tử bậc thấp (Drop Non-Dominant Terms)

Một hàm có vòng lặp lồng nhau $O(n^2)$ đi kèm với một vòng lặp đơn $O(n)$ bên ngoài. Tổng số phép tính là $O(n^2 + n)$.

Khi $n = 10,000$, phần $n^2$ sẽ là 100,000,000, trong khi phần $n$ chỉ là 10,000. Phần $n$ trở nên quá nhỏ bé và không đáng kể. Do đó, $O(n^2 + n)$ được rút gọn gọn gàng thành $O(n^2)$.

Nắm vững Time Complexity và Big-O giống như bạn được trang bị một hệ thống radar. Trước khi gõ bất kỳ một dòng code nào xử lý dữ liệu lớn, radar trong đầu bạn sẽ ngay lập tức "báo động" nếu bạn chuẩn bị viết một đoạn logic $O(n^2)$.

Nhưng thời gian không phải là tài nguyên duy nhất chúng ta cần quản lý. Để chạy nhanh, đôi khi máy tính phải trả giá bằng việc "ngốn" rất nhiều RAM. Trong bài tiếp theo, chúng ta sẽ khám phá bài toán đánh đổi giữa bộ nhớ và tốc độ: Độ phức tạp không gian (Space Complexity) & Bài toán Trade-off.