Giải SBT Tin học 11 KNTT Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán có đáp án
Xem toàn bộ quiz

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

1/7

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.

0/3000 ký tự
Giải thích

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