Tính độ phức tạp của các hàm thời gian sau: a) T(n) = n + 2log n

Giải SBT 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

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").