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

Trang trước Trang sau

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:

Xem thêm các bài giải sách bài tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:

Xem thêm các tài liệu học tốt lớp 11 hay khác:

Trang trước Trang sau
Giải bài tập lớp 11 Kết nối tri thức khác