Câu hỏi:

30/11/2024 349

PHẦN II. Câu trắc nghiệm đúng sai. Thí sinh trả lời từ câu 1 đến câu 2. Trong mỗi ý a), b), c), d) ở mỗi câu, thí sinh chọn đúng hoặc sai

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

a) O(1)

b) O(log n)

c) O(n)

d) O(n²)

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

a) Sai, O(1) biểu thị độ phức tạp hằng số, không phụ thuộc vào kích thước đầu vào nnn, trong khi độ phức tạp của chương trình 1 phụ thuộc tuyến tính vào nnn.

b) Sai. O(log n) chỉ đúng cho các thuật toán mà thời gian tính toán tăng tỷ lệ logarit với nnn, điều này không đúng trong chương trình 1.

c) Đúng. O(n) nghĩa là thời gian tính toán tăng tuyến tính với kích thước đầu vào nnn, phù hợp với hàm T1(n)=n+3T_1(n) = n + 3T1​(n)=n+3.

d) Sai. O(n²) mô tả độ phức tạp bậc hai, thường xuất hiện ở các thuật toán có vòng lặp lồng nhau, điều này không áp dụng cho chương trình 1.

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

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