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.

Câu hỏi trong đề: 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 !!

Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa... kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 70k).

Quảng cáo

Trả lời:

Giải bởi Vietjack

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

Combo - Sổ tay kiên thức trọng tâm Toán, Lí, Hóa dành cho 2k7 VietJack

Sách - Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia Hà Nội 2025 cho 2k7 VietJack

Sách Combo - Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia TP Hồ Chí Minh (2 cuốn) - 2025 cho 2k7 VietJack

Sách - Tuyển tập 15 đề thi Đánh giá tư duy Đại học Bách Khoa Hà Nội 2025 cho 2k7 VietJack

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Xem đáp án » 27/11/2023 1,307

Câu 2:

Xem đáp án » 13/07/2024 828

Câu 3:

Xem đáp án » 27/11/2023 502

Câu 4:

Xem đáp án » 27/11/2023 338

Câu 5:

Xem đáp án » 13/07/2024 240

Câu 6:

Xem đáp án » 13/07/2024 238