Sách bài tập Tin học 11 Bài 5 (Cánh diều): Đánh giá thuật toán

Giải SBT Tin học 11 Bài 5: Đánh giá thuật toán

Câu F^cs17 trang 51 SBT Tin học 11: Những phát biểu nào dưới đây là SAI?

Lời giải:

Phát biểu 2 và 3 sai. Khi n đủ lớn, 2" sẽ lớn hơn n rất nhiều và tương tự, n’ sẽ lớn hơn n và n.log,n rất nhiều.

Em hãy xây dựng thuật toán để giải quyết bài toán trên với độ phức tạp.

1) O(n).

2) O(1).

Lời giải:

1) Dùng vòng lặp từ 1 đến n để cộng từng giá trị bình phương vào biến tổng S.

2) Dùng công thức

1) O(nlogn).

2) O(n).

Lời giải:

1) Sắp xếp lại danh sách theo thứ tự giảm dần bằng phương pháp sắp xếp nhanh (hàm Sorted ( ) có độ phức tạp O(n.log,n )) rồi in ra phần tử ở vị trí thứ hai.

2) Khởi tạo hai biến max1 = 0 và max2 = 0 tượng trưng cho giá trị lớn thứ 0 nhất và lớn thứ hai trong danh sách A, ta tiến hành duyệt và xét lần lượt từng phần tử v của A:

Nếu max1 < v, ta cập nhật max2 = max1 và max1 = v.

Ngược lại, ta có thể suy ra max1>v(max1 không thể bằng v vì các phần tử trong danh sách A khác nhau từng đôi một). Ta so sánh max2 và v. Nếu max2 < v thì ta cập nhật max2 = v.

Câu F^cs20 trang 52 SBT Tin học 11: Xác định độ phức tạp của đoạn chương trình sau, với giá trị N>0 được cho ở dữ liệu đầu vào:

Lời giải:

Vì giá trị của i bị giảm đi một nửa sau mỗi bước và vòng lặp sẽ dừng khi i = 0, nên độ phức tạp của chương trình là O(log,N).

Câu F^cs21 trang 52 SBT Tin học 11: Xác định độ phức tạp của đoạn chương trình sau, với giá trị n > 0 được cho ở dữ liệu đầu vào:

Lời giải:

Sau khi kết thúc lượt chạy i = 0, giá trị j sẽ tăng lên bằng n. Ở các lượt chạy sau đó của i thì vòng lặp while bên trong sẽ không được thực thi, nên độ phức tạp của cả chương trình chỉ là O(n).