Đánh giá độ phức tạp thời gian thuật toán
Tóm tắt
Bài học hướng dẫn ước lượng T(n), nhận diện phép toán tích cực và xác định O-lớn.
Hiểu bài
Thời gian chạy T(n) có thể được ước lượng bằng số đơn vị thời gian của các phép tính cơ bản, trong đó phép toán tích cực là phép được thực hiện nhiều lần và chi phối mức tăng. Kí hiệu O-lớn biểu diễn bậc tăng theo kích thước dữ liệu. Các bậc thường gặp gồm O(1), O(log n), O(n), O(n²), O(n^k), O(a^n) và O(n!). Khi xác định bậc, giữ thành phần tăng nhanh nhất. Chẳng hạn:
T(n) = 2n(n - 2) + 4 = 2n² - 4n + 4, nên có bậcO(n²).T(n) = n³ + 5n - 3, nên có bậcO(n³).