1. Kiến thức trọng tâm
Độ phức tạp thời gian cho biết thời gian chạy của thuật toán tăng lên như thế nào khi kích thước dữ liệu đầu vào tăng lên. Đánh giá độ phức tạp giúp so sánh và lựa chọn thuật toán phù hợp, đặc biệt khi xử lí dữ liệu lớn. Hai thuật toán cho cùng kết quả có thể chênh lệch thời gian chạy rất lớn.
Độ phức tạp thường biểu diễn bằng kí hiệu O lớn, mô tả tốc độ tăng của số phép toán cơ bản theo kích thước đầu vào n. Các độ phức tạp thường gặp là O(1) (hằng số), O(n) (tuyến tính), O(n^2) (bình phương) và O(log n) (lôgarit, tăng rất chậm). Ví dụ, tìm kiếm tuần tự có độ phức tạp O(n) trong trường hợp xấu nhất, còn tìm kiếm nhị phân có độ phức tạp O(log n).
Khi đánh giá, thường xét trường hợp xấu nhất, tức thuật toán chạy lâu nhất, vì nó cho giới hạn về thời gian. Sắp xếp nổi bọt và sắp xếp chọn đều có độ phức tạp O(n^2) trong trường hợp xấu nhất, nghĩa là khi n tăng gấp đôi, thời gian chạy tăng khoảng bốn lần.
2. Ví dụ minh họa
Ví dụ: so sánh hai thuật toán tìm kiếm trên dãy có n = 1 000 000 phần tử. Với tìm kiếm tuần tự, trường hợp xấu nhất phải duyệt hết cả triệu phần tử, tức khoảng 1 000 000 lần so sánh. Với tìm kiếm nhị phân, mỗi bước loại bỏ một nửa khoảng tìm kiếm, nên sau khoảng log2(1 000 000) ≈ 20 lần so sánh là tìm ra đáp án. Nếu mỗi lần so sánh mất một phần triệu giây, tìm kiếm tuần tự mất khoảng một giây, tìm kiếm nhị phân chỉ mất khoảng hai mươi phần triệu giây. Vì vậy, chọn thuật toán có độ phức tạp thấp rất quan trọng khi dữ liệu lớn.
3. Ghi nhớ
- Độ phức tạp thời gian cho biết thời gian chạy tăng như thế nào khi kích thước dữ liệu tăng.
- Kí hiệu O lớn mô tả tốc độ tăng trưởng:
O(1),O(log n),O(n),O(n^2). - Thường đánh giá theo trường hợp xấu nhất để có giới hạn an toàn về thời gian.
- Thuật toán có độ phức tạp thấp hơn chạy nhanh hơn nhiều khi dữ liệu lớn.