Giáo án và PPT Khoa học máy tính 11 cánh diều Bài 5: Đánh giá thuật toán

BÀI 5. ĐÁNH GIÁ THUẬT TOÁN

HOẠT ĐỘNG KHỞI ĐỘNG

GV đặt câu hỏi: Theo em, một thuật toán như thế nào thì được xem là chạy nhanh/chạy chậm?

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Các khái niệm cơ bản

GV yêu cầu học sinh trao đổi: Tính hiệu quả của thuật toán dựa trên những tiêu chí nào? 

Sản phẩm dự kiến:

Hiệu quả thuật toán được đánh giá theo cả hai tiêu chí: tiết kiệm thời gian và tiết kiệm không gian nhớ.

Hoạt động 2: Độ phức tạp thời gian của thuật toán      

Thế nào là độ phức tạp thời gian của thuật toán?

Phép toán sơ cấp là gì? 

Sản phẩm dự kiến:

- Độ phức tạp thời gian của thuật toán là kết quả ước lượng thời gian thực hiện các chương trình cài đặt thuật toán để xử lí một lượng dữ liệu đầu vào có độ lớn n.

- Phép toán sơ cấp là phép toán có thời gian thực hiện không lớn hơn một hằng số nào đó, không phụ thuộc n (n là kích thước dữ liệu đầu vào).

Hoạt động 3: Ví dụ về độ phức tạp thời gian hằng số và độ phức tạp thời gian tuyến tính

Độ phức tạp thời gian hằng số, độ phức tạp thời gian tuyến tính là gì ?

Sản phẩm dự kiến:

- Thuật toán có độ phức tạp thời gian hằng số khi mà số phép toán cần thực hiện không phụ thuộc kích thước n của dữ liệu đầu vào.

- Thuật toán có độ phức tạp thời gian tuyến tính nếu số phép toán cần thực hiện là hàm tuyến tính của n (n là kích thước dữ liệu đầu vào).

Hoạt động 4: Kí pháp và các bậc độ phức tạp thời gian

Thế nào là cách ước lượng làm già thêm?

Sản phẩm dự kiến:

- Số phép toán cần thiết để thực hiện thuật toán không chỉ phụ thuộc kích thước n của dữ liệu đầu vào mà còn phụ thuộc vào việc may mắn gặp trường hợp dễ, ít việc phải làm hay không may gặp trường hợp khó, nhiều việc phải làm hơn.

- Ước lượng làm già thêm là cách ước lượng đảm bảo rằng trong thực tế sẽ không có trường hợp nào vượt quá ước lượng đã đưa ra.

Cho biết O lớn được sử dụng như thế nào trong thuật toán.

Sản phẩm dự kiến:

- Nếu phép toán sơ cấp cần thực hiện không vượt quá một hằng số C, không phụ thuộc n → Độ phức tạp thời gian là hằng số T(n) = O(1).

- Nếu phép toán sơ cấp cần thực hiện không vượt quá một hàm số tuyến tính của n, T(n) ≤ C₁n + C₂ (C₁, C₂ là hằng số) → Độ phức tạp thời gian là tuyến tính T(n) = O(n). 

- Một số công thức liên quan:

Công thức 1: Áp dụng cho hai cấu trúc điều khiển được thực hiện tuần tự.

Nếu f₁(n) = O(g₁(n)) và f₂(n) = O(g₂(n)) 

thì f₁(n) + f₂(n) = O(max(g₁(n), g₂(n)).

Công thức 2: Áp dụng cho hai cấu trúc điều khiển lồng nhau.

Nếu f₁(n) = O(g₁(n)) và f₂(n) = O(g₂(n))

thì f₁(n) × f₂(n) = O(g₁(n)× g₂(n)).

Hoạt động 5: Các quy tắc khi ước lượng thời gian thực hiện thuật toán

GV đặt câu hỏi hướng dẫn học sinh tìm hiểu: Trình bày các quy tắc khi ước lượng thời gian thực hiện thuật toán.

Sản phẩm dự kiến:

Quy tắc chung

- Khi tính đếm số phép toán cần thực hiện, các quy tắc ước lượng cho phép bỏ bớt những phần có bậc lớn thấp hơn, chỉ giữ lại những phần có bậc lớn cao nhất và các hằng số nhân C đều coi là 1.

- Mô tả thuật toán chỉ sử dụng ba cấu trúc: cấu trúc tuần tự, cấu trúc rẽ nhánh, cấu trúc lặp.

- Lồng bên trong các cấu trúc rẽ nhánh và cấu trúc lặp lại là các dãy phép toán tuần tự khác → Cần ước lượng số phép toán từ bên trong trở ra ngoài.

Lời gọi hàm

- Hàm bên trong chương trình thực chất là một chương trình con, thực hiện một thuật toán cụ thể.

- Ước lượng độ phức tạp thời gian của một lời gọi hàm được chia làm hai trường hợp:

+ Lời gọi các hàm toán học sơ cấp, các hàm thư viện… với đầu vào là các giá trị cụ thể không phụ thuộc n → T(n) = O(1).

+ Lời gọi hàm trong các trường hợp còn lại sẽ được ước lượng độ phức tạp như với một thuật toán.

Cấu trúc tuần tự và quy tắc lấy max

- Cấu trúc tuần tự là một dãy gồm C phép toán; C là số xác định, không phụ thuộc n.

+ Nếu tất cả C phép toán là sơ cấp → độ phức tạp thời gian là T(n) = O(1).

+ Trái lại, thời gian thực hiện bằng ước lượng lớn nhất trong số các ước lượng của phép toán có trong dãy.

Cấu trúc rẽ nhánh và quy tắc lấy max

- Khi thực thi một cấu trúc rẽ nhánh sẽ phải kiểm tra điều kiện và thực hiện một trong số các nhánh. 

- Việc kiểm tra điều kiện là tính giá trị biểu thức logic gồm biểu thức số học và một phép so sánh → T(n) = O(1).

- Độ phức tạp thời gian của cấu trúc rẽ nhánh là độ phức tạp lớn nhất trong các độ phức tạp thời gian của các nhánh.

Ví dụ: 

Cấu trúc vòng lặp và quy tắc nhân

- Khi thực hiện một cấu trúc vòng lặp sẽ phải kiểm tra điều kiện và thực hiện hiện thân vòng lặp.

- Thân vòng lặp là một cấu trúc tuần tự các phép toán.

- Thời gian thực hiện cấu trúc vòng lặp được tính bằng số lần lặp nhân với tổng thời gian kiểm tra điều kiện lặp và thời gian thực hiện thân vòng lặp.

Ví dụ: 

HOẠT ĐỘNG LUYỆN TẬP

Câu 1. Lời gọi các hàm sơ cấp, các hàm thư viện… với đầu vào là giá trị cụ thể không phụ thuộc n có độ phức tạp thời gian là

A. T(n) = O(1)      B. T(n) = O(n)       C. T(n) = O(n!)       D. T(n) = O(n²)

Câu 2. Phép toán nào sau đây không phải là phép toán sơ cấp

A. phép so sánh

B. các hàm với đầu vào là giá trị cụ thể không phụ thuộc n

C. phép toán số học

D. phép lựa chọn

Câu 3. Không thể đánh giá thuật toán qua chương trình cài đặt thuật toán vì

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

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

(3) Không khả thi nếu muốn chọn cách tính thời gian thực thi trung bình. 

(4) Thời gian chạy chương trình phụ thuộc kích thước dữ liệu đầu vào.

Số đáp án đúng là

A. 1                      B. 2                      C. 3                      D. 4

Câu 4. Cho ví dụ sau đây: Chương trình tìm kiếm một số x trong dãy số gồm 20 chữ số mất khoảng 2s, nếu dãy số tăng lên 2000 số thì thời gian chạy mất khoảng 20s. Yếu tố ảnh hưởng đến thời gian chạy chương trình trên là

A. kích thước dữ liệu đầu ra                         B. kích thước dữ liệu đầu vào

C. kĩ năng lập trình                                               D. chương trình khác nhau

Câu 5. Ước lượng thời gian chạy chương trình sau:

n = 100

C = 0

for k in range (n):

                   C = C + 1

print (C)

A. T(n) = 3                                                  B. T(n) = n – 1      

C. T(n) = n + 3                                            D. T(n) = n + 1

Đáp án gợi ý:

HOẠT ĐỘNG VẬN DỤNG

GV yêu cầu HS hoàn thành Vận dụng SGK trang 112:

Câu 1. Xét bài toán sắp xếp dãy số. Em 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.

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.