Với Luyện tập 1 trang 114 giải SGK Tin học 11 Kết nối tri thức chi tiết trong Bài 24: Đánh giá độ phức tạp thời gian thuật toán giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Tin học 11. Mời các bạn đón xem:
Xác định độ phức tạp thời gian cho chương trình sau
Luyện tập 1 trang 114 Tin học 11: 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)
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)
Xem thêm các bài giải SGK Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Câu hỏi trang 114 Tin học 11: Tính độ phức tạp của các hàm thời gian sau:
Luyện tập 1 trang 114 Tin học 11: Xác định độ phức tạp thời gian cho chương trình sau:
Luyện tập 2 trang 114 Tin học 11: Xác định độ phức tạp thời gian tính toán cho chương trình sau:
Xem thêm các bài giải SGK Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Bài 22: Thực hành bài toán sắp xếp
Bài 23: Kiểm thử và đánh giá chương trình
Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán
Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình
Bài 27: Thực hành thiết kế chương trình theo phương pháp làm mịn dần
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
- Người đại diện: Nguyễn Thanh Tuyền
- Số giấy chứng nhận đăng ký kinh doanh: 0108307822, ngày cấp: 04/06/2018, nơi cấp: Sở Kế hoạch và Đầu tư thành phố Hà Nội.
2021 © All Rights Reserved.
