Tính độ phức tạp của các hàm thời gian sau: a) T(n) = n + 2log n
Câu 25.1 trang 77 SBT Tin học 11: Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = n + 2log n.
c) T(n) = 2100
b) T(n) = n2 + 3nlogn + 2n.
d) T(n) = 2n+1.
a) T(n) = n + 2log n ≤ 3n với n ≥ 1. Vậy T(n) = O(n).
b) T(n) = n2 + 3nlogn +2n ≤ 6n với n ≥ 1. Vậy T(n) = O(n).
c) T(n) = O(1), độ phức tạp hằng số.
d) T(n) = 2n+1 = 2.2" = O(2").
Xem thêm các bài giải SBT Tin học 11 Kết nối tri thức hay, chi tiết khác: