Slide bài giảng Khoa học máy tính 11 cánh diều Chủ đề F(CS) Bài 5: Đánh giá thuật toán

Tóm lược nội dung

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

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

GV đặt câu hỏi: Theo em, thuật toán nào thì được coi là nhanh hay chậm?

NỘI DUNG BÀI HỌC GỒM

• Các khái niệm cơ bản
• Độ phức tạp thời gian của thuật toán
• 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
• Kí pháp và các bậc độ phức tạp thời gian
• Các quy tắc khi ước lượng thời gian thực hiện thuật toán
• Luyện tập
• Vận dụng

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 được xác định bởi những tiêu chí nào?

Nội dung gợi ý:

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

Độ phức tạp thời gian của thuật toán được hiểu như thế nào? Khái niệm về phép toán sơ cấp là gì?

Nội dung gợi ý:

- Độ 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ố và độ phức tạp thời gian tuyến tính là gì?

Nội dung gợi ý:

- 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

Cách ước lượng làm già thêm là gì?

Nội dung gợi ý:

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

Hãy cho biết O lớn được sử dụng trong thuật toán như thế nào?

Nội dung gợi ý:

- 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: Nêu các quy tắc khi ước lượng thời gian thực hiện thuật toán.

Nội dung gợi ý:

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: Truy vấn dữ liệu có nghĩa là:

A. In dữ liệu

B. Cập nhật dữ liệu

C. Tìm kiếm và hiển thị dữ liệu

D. Xóa các dữ liệu không cần đến nữa

Câu 2: Nếu những bài toán phức tạp, liên quan tới nhiều bảng, ta sử dụng:

A. Mẫu hỏi    

B. Bảng    

C. Báo cáo     

D. Biểu mẫu

Câu 3: Để hiển thị một số bản ghi nào đó trong cơ sở dữ liệu, thống kê dữ liệu, ta dùng:

A. Mẫu hỏi     

B. Câu hỏi     

C. Liệt kê     

D. Trả lời

Câu 4: Các chế độ làm việc với mẫu hỏi là:

A. Mẫu hỏi

B. Mẫu hỏi và thiết kế

C. Trang dữ liệu và thiết kế

D. Trang dữ liệu và mẫu hỏi

Câu 5: Kết quả thực hiện mẫu hỏi có thể tham gia vào việc tạo ra:

A. Bảng, biểu mẫu, mẫu hỏi hay báo cáo

B. Bảng, biểu mẫu khác, mẫu hỏi khác hay các trang khác

C. Bảng, biểu mẫu, mẫu hỏi khác hay báo cáo

D.Bảng, biểu mẫu, mẫu hỏi khác

Đá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. Trong bài toán sắp xếp dãy số, khi nào ta gặp trường hợp thuận lợi nhất và số phép toán cần thực hiện là ít nhất?

Câu 2. Hãy ướ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) Khi đầu vào là dãy ngẫu nhiên.

b) Khi đầu vào là dãy giảm dần.