1. Kiến thức trọng tâm
Độ phức tạp thời gian đo lượng thời gian chạy của thuật toán khi kích thước dữ liệu đầu vào tăng lên. Người ta thường dùng kí hiệu O lớn để mô tả tốc độ tăng trưởng, ví dụ O(1), O(log n), O(n), O(n log n), O(n²).
Để xác định độ phức tạp, ta đếm số lần thực hiện các phép toán cơ bản như gán, so sánh, cộng, trừ theo kích thước đầu vào n, rồi giữ lại thành phần tăng nhanh nhất, bỏ hằng số và hệ số.
Một số trường hợp thường gặp: duyệt toàn bộ danh sách một lần là O(n); hai vòng lặp lồng nhau, mỗi vòng duyệt n phần tử, là O(n²); chia đôi khoảng tìm kiếm mỗi bước là O(log n); thuật toán chỉ làm một số phép toán cố định là O(1).
Khi thực hành, cần phân biệt trường hợp tốt nhất, trung bình và xấu nhất. Chẳng hạn tìm kiếm tuyến tính có trường hợp tốt nhất O(1) khi phần tử cần tìm ở đầu danh sách, nhưng trường hợp xấu nhất là O(n).
2. Ví dụ minh họa
Ví dụ 1: đoạn chương trình tính tổng các số từ 1 đến n bằng một vòng lặp cộng dồn. Mỗi lần lặp thực hiện một phép cộng và một phép gán, tổng cộng n lần. Vì vậy độ phức tạp là O(n).
Ví dụ 2: đoạn chương trình in bảng cửu chương gồm hai vòng lặp lồng nhau, vòng ngoài chạy từ 1 đến 9, vòng trong cũng chạy từ 1 đến 9, tổng cộng 81 lần in. Nếu tổng quát hoá với n hàng và n cột thì số lần thực hiện là n × n, độ phức tạp là O(n²).
Ví dụ 3: tìm kiếm nhị phân trên danh sách đã sắp xếp có 16 phần tử chỉ cần tối đa 5 lần so sánh, vì mỗi bước loại bỏ một nửa danh sách. Độ phức tạp là O(log n).
3. Ghi nhớ
- Độ phức tạp thời gian mô tả xu hướng tăng của thời gian chạy theo n.
- Đếm số lần thực hiện phép toán cơ bản, giữ thành phần tăng nhanh nhất.
- O(1) < O(log n) < O(n) < O(n log n) < O(n²).
- Luôn nêu rõ đang xét trường hợp tốt nhất, trung bình hay xấu nhất.