Bài 5: Đánh giá thuật toán

Chủ đề F^cs: Giải quyết vấn đề với sự trợ giúp của máy tính – Kĩ thuật lập trình – Bài 5: Đánh giá thuật toán – sách bài tập trang 51 lớp 11 Khoa học máy tính – Cánh Diều, mời các em tham khảo cùng Bumbii.

Chủ đề F^cs: Giải quyết vấn đề với sự trợ giúp của máy tính – Kĩ thuật lập trình – Bài 5: Đánh giá thuật toán

Câu F^CS17

Những phát biểu nào dưới đây là SAI?

1) O(n + m + p) = O(max(m, n, p)) với m, n, p được cho ở dữ liệu đầu vào.

2) O(2ⁿ + n²) = O(n²) với n được cho ở dữ liệu đầu vào.

3) O(n + n² +n.log₂n) = O(n.log₂n) với n được cho ở dữ liệu đầu vào.

4) O(2022) = O(1).

Trả lờ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.

Câu F^CS18

Xét bài toán: Tính tổng bình phương các số tự nhiên từ 1 đến n, với n là một số tự nhiên lớn hơn 0. Nói cách khác, tính giá trị S = 1² + 2² + … + (n – 1)² + n².

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).

Trả lờ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:

Câu F^CS19

Xét bài toán: Cho danh sách các số nguyên A = (a₁, a₂, … , a_n) khác nhau từng đôi một. Xác định phần tử có giá trị lớn thứ hai trong danh sách A.

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(nlog₂n).

2) O(n).

Trả lờ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ứ 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

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:

Trả lờ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

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:

Trả lờ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).

Xem các bài giải khác: Giải Bài Tập SBT Lớp 11 Khoa Học Máy Tính Cánh Diều

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech