Đánh giá độ phức tạp thời gian thuật toán

Hiểu bài

Thời gian chạy có thể được ước lượng bằng số đơn vị thời gian, mỗi đơn vị tương ứng một phép tính đơn. Phép toán tích cực là phép toán được thực hiện nhiều lần và chi phối sự tăng của thời gian khi kích thước dữ liệu n tăng. Vòng lặp đơn thường tạo số lần thực hiện tỉ lệ với n; hai vòng lặp lồng nhau, mỗi vòng chạy theo n, thường tạo bậc n².

Kí hiệu O-lớn biểu diễn bậc tăng chủ đạo. Khi phân tích hàm thời gian, giữ thành phần tăng nhanh nhất và bỏ hệ số hằng cùng thành phần bậc thấp. Ví dụ:

• T(n) = 2n(n - 2) + 4 = 2n² - 4n + 4, nên T(n) = O(n²).
• T(n) = n³ + 5n - 3, nên T(n) = O(n³).

Các bậc thường gặp gồm O(1), O(log n), O(n), O(n²), đa thức, luỹ thừa và giai thừa.