Câu hỏi:

30/11/2024 464

Độ phức tạp thời gian của chương trình 2 trong Hình 24.2, với tổng thời gian tính toán là T2(n)=n2+3T_2(n) = n^2 + 3T2​(n)=n2+3, được đánh giá là:

a) O(n)

b) O(n²)

c) O(log n)

d) O(1)

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

a) Sai. O(n) biểu thị độ phức tạp tuyến tính, không phù hợp với T2(n)=n2+3T_2(n) = n^2 + 3T2​(n)=n2+3, vì thời gian tính toán của chương trình 2 tăng theo bậc hai của nnn.

b) Đúng. O(n²) biểu thị độ phức tạp bậc hai, phù hợp với cấu trúc vòng lặp lồng nhau của chương trình 2.

c) Sai. O(log n) biểu thị độ phức tạp logarit, thường gặp ở các thuật toán chia để trị, không áp dụng cho chương trình 2.

d) Sai. O(1) nghĩa là độ phức tạp hằng số, không thay đổi với kích thước đầu vào, không đúng với chương trình 2.

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

Câu 1

Lời giải

Đáp án: B

Giải thích: Quy tắc cộng được áp dụng khi tính độ phức tạp thời gian của hai chương trình nối tiếp nhau, lấy giá trị độ phức tạp lớn nhất

Câu 2

Lời giải

Đáp án: A

Giải thích: O(n)O(n)O(n) biểu thị độ phức tạp tuyến tính, tức là thời gian chạy tăng tuyến tính với kích thước đầu vào nnn.

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 4

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 5

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 6

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP