Câu hỏi:

20/04/2023 336

Quan sát và thực hiện đánh giá thời gian chạy của các chương trình 1 và 2 trong Hình 24.2. Từ đó biết và hiểu được cách đánh giá thời gian thực hiện chương trình.

Xem lời giải

Câu hỏi trong đề: Giải SGK Tin học 11 KNTT Bài 24. Đánh giá độ phức tạp thời gian thuật toán có đáp án !!

Giao bài

Quảng cáo

Trả lời:

Giải bởi Vietjack

Chương trình 1: Thời gian thực hiện chương trình là T1=T1(n)=2+n+1=n+3 (đơn vị thời gian)

Chương trình 2: Thời gian thực hiện chương trình là T2=T1(n)=2+n²+1=n²+3 (đơn vị thời gian)

Đang tải chế độ Học...

Hot: 1000+ đề thi cuối kì 1 lớp 1-12 đầy đủ các môn (Update 2026) (chỉ từ 60k). Tải ngay

Dành cho bạn Hot

Lớp 11 Toán

112 người thi tuần này

Trắc nghiệm Đường thẳng và mặt phẳng song song lớp 11 (có đúng sai, trả lời ngắn)

20 câu 1.2 K lượt thi Thi ngay →

Lớp 11 Vật lý

205 người thi tuần này

Trắc nghiệm Mô tả sóng lớp 11 (có đáp án)

10 câu 6.3 K lượt thi Thi ngay →

Lớp 11 Hóa học

141 người thi tuần này

Trắc nghiệm Nitrogen lớp 11 (có đáp án - phần 1)

15 câu 4.2 K lượt thi Thi ngay →

Lớp 11 Tiếng Anh

143 người thi tuần này

Đề cương ôn tập giữa kì 1 Tiếng Anh 11 Global Success có đáp án

50 câu 1.2 K lượt thi Thi ngay →

Lớp 11 Sinh học

161 người thi tuần này

15 câu Trắc nghiệm Sinh học 11 Kết nối tri thức Bài 8 có đáp án

15 câu 3.2 K lượt thi Thi ngay →

Lớp 11 Lịch sử

1,314 người thi tuần này

25 câu Trắc nghiệm Lịch Sử 11 Kết nối tri thức Bài 1 có đáp án

25 câu 20.4 K lượt thi Thi ngay →

Lớp 11 Tin học

745 người thi tuần này

15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 1 có đáp án

15 câu 9.8 K lượt thi Thi ngay →

Lớp 11 Giáo dục Kinh tế và Pháp luật

158 người thi tuần này

16 câu Trắc nghiệm Kinh tế pháp luật 11 Kết nối tri thức Bài 2 có đáp án

16 câu 3.9 K lượt thi Thi ngay →

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

Câu 1

Xác định độ phức tạp thời gian tính toán cho chương trình sau:

n = 1000

sum = 0

i = 1

while i <n;

i = i*2

sum = sum + 1

print (sum)

Xem đáp án

Lời giải

Chương trình trên tính số lần lặp cần thiết để i lớn hơn n bằng cách nhân i với 2 trong mỗi lần lặp, sau đó tăng biến sum lên 1. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng while và các phép toán trong vòng lặp.

Vòng while: Vòng lặp này chạy cho đến khi i >= n, và giá trị ban đầu của i là 1. Trong mỗi lần lặp, i được nhân với 2, vậy số lần lặp là log2(n) (vì sau mỗi lần nhân i với 2, giá trị của i sẽ gấp đôi). Ví dụ, nếu n = 1000 thì số lần lặp là log2(1000) ≈ 10.

Các phép toán trong vòng lặp:

Phép gán i = i * 2: Đây là phép nhân, có độ phức tạp là O(1).

Phép gán sum = sum + 1: Đây là phép gán giá trị vào biến sum, có độ phức tạp là O(1).

Vậy tổng độ phức tạp thời gian của chương trình là O(log n), hay O(log2(1000)) ≈ O(10)

Câu 2

Xác định độ phức tạp thời gian cho chương trình sau:

n = 1000

s = 0

for i in range (n);

s = s + i*(i+1)

print (s)

Xem đáp án

Lời giải

Chương trình trên tính tổng các giá trị i*(i+1) trong khoảng từ 0 đến n-1 và lưu kết quả vào biến s. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng for và các phép toán trong vòng lặp.

Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1.000. Vậy số lần lặp là n, hay 1.000 lần.

Các phép toán trong vòng lặp:

Phép gán s = s + i*(i+1): Đây là phép gán giá trị vào biến s, có độ phức tạp là O(1).

Phép toán i*(i+1): Đây là phép nhân và cộng, có độ phức tạp là O(1).

Vậy tổng độ phức tạp thời gian của chương trình là O(n), hay O(1.000)

Câu 3