Luyện tập 2 trang 114 SGK Tin học 11 Kết nối tri thức
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)
Hướng dẫn giải chi tiết Luyện tập 2
- 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).
-- Mod Tin Học 11 HỌC247
Bài tập SGK khác
Chưa có câu hỏi nào. Em hãy trở thành người đầu tiên đặt câu hỏi.
