Chủ đề Fcs : 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 giáo khoa trang 107 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ủ đề Fcs : 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
KHỞI ĐỘNG
Theo em, một thuật toán như thế nào thì được xem là chạy nhanh/chạy chậm?
Lời giải:
Tốc độ của một thuật toán thường được đánh giá dựa trên độ phức tạp thời gian của nó. Độ phức tạp càng thấp thì chạy càng nhanh.
LUYỆN TẬP
Em hãy cho ví dụ một lời gọi hàm được tính là phép toán sơ cấp và một lời gọi hàm không được tính là phép toán sơ cấp.
Lời giải:
- Ví dụ lời gọi hàm phép toán sơ cấp:
sqrt(10);sin(5);…
- Ví dụ lời gọi hàm không là phép toán sơ cấp:
max(a),min(a),sum(a),… do a ở đây là 1 dãy số.
VẬN DỤNG
Câu 1. Xét bài toán sắp xếp dãy số. Hãy cho biết khi nào ta có trường hợp thuận lợi nhất, số phép toán cần làm là ít nhất?
Lời giải:
Trường hợp thuận lợi nhất: dãy đã xếp đúng thứ tự mong muốn, số phép toán cần làm là ít nhất. Chú ý rằng số phép toán cần làm không phải bằng 0 mà ít nhất cũng là n – 1 (phép so sánh).
Câu 2. Ước lượng số phép toán sơ cấp cần thực hiện để tìm số lớn nhất trong dãy số:
a) Đầu vào là dãy ngẫu nhiên.
b) Đầu vào là dãy giảm dần.
Lời giải:
a) Đầu vào là dãy ngẫu nhiên: O(n).
b) Đầu vào là dãy giảm dần: n – 1.
LUYỆN TẬP
Câu 1. Tại sao không thể đánh giá thuật toán qua chương trình cài đặt thuật toán?
Lời giải:
Không thể đánh giá thuật toán qua chương trình cài đặt thuật toán vì sẽ dẫn đến các vấn đề:
- Phải lập trình và chạy thử chương trình của tất cả các thuật toán cần so sánh.
- Thời gian đo được phụ thuộc vào nhiều yếu tố không liên quan tới thuật toán: Phần cứng máy tính, ngôn ngữ lập trình, chương trình dịch, kĩ năng lập trình của người viết.
- Không khả thi nếu muốn chọn cách tính thời gian thực thi trung bình.
Câu 2. Khi nào áp dụng quy tắc lấy max?
Lời giải:
Áp dụng quy tắc lấy max với cấu trúc tuần tự (dãy câu lệnh) và cấu trúc rẽ nhánh.
Câu 3. Quy tắc nhân áp dụng cho cấu trúc vòng lặp là gì?
Lời giải:
Quy tắc nhân áp dụng cho cấu trúc vòng lặp là: Ước lượng thời gian thực hiện tính bằng số lần lặp nhân với thời gian lớn nhất thực hiện một lệnh trong vòng lặp.
Xem các bài giải khác: Giải Bài Tập Sách Giáo Khoa Tin Học 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
