Tính độ phức tạp của các hàm thời gian sau: T(n) = n + 2log n
Tính độ phức tạp của các hàm thời gian sau:
Sách bài tập Tin học 11 Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Kết nối tri thức
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.
Lời giải:
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").
Lời giải sách bài tập Tin học 11 Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán hay khác: