Đề bài
Phương án nào sau đây nêu đúng độ phức tạp của hàm thời gian $T\left( n \right) = {n^5} + 5n - 3$ ?
${\rm{O}}\left( n \right)$.
${\rm{O}}\left( {{n^3}} \right)$.
${\rm{O}}\left( 1 \right)$.
${\rm{O}}\left( {{n^5}} \right)$.
Đáp án đúng: D
Xem lời giải
Lời giải chi tiết
Để xác định độ phức tạp của hàm thời gian T(n) = n5 + 5n - 3, ta cần tìm bậc của đa thức này lớn hơn tất cả các bậc còn lại. Điều này được thực hiện bằng cách xem xét các hạng tử của đa thức:
1. Hạng tử chính: n5
2. Các hạng tử phụ: 5n và -3
Đối với hàm thời gian và độ phức tạp tính toán, khi n càng lớn thì hạng tử bậc cao nhất sẽ chi phối độ phức tạp của hàm số. Trong trường hợp này, hạng tử n5 là hạng tử bậc cao nhất. Do đó, ta có thể nói rằng hàm thời gian T(n) có độ phức tạp là O(n5).
Vậy, phương án đúng là:
D. O(n5)
Chú ý khi giải
Khi giải các bài tập về độ phức tạp tính toán, lưu ý rằng:
- Hãy xác định bậc của hạng tử lớn nhất trong đa thức biểu diễn hàm thời gian.
- Bỏ qua các hệ số không ảnh hưởng đến độ phức tạp bậc lớn.
- Khi n rất lớn, chỉ cần quan tâm đến hạng tử có bậc cao nhất.