Video giảng Khoa học máy tính 11 cánh diều 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

Thông qua video này, các em sẽ nắm được các kiến thức và kĩ năng như sau:

• Trình bày được sơ lược khái niệm độ phức tạp thời gian của thuật toán. Nêu được ví dụ minh họa.
• Biết được kí pháp O lớn và các bậc độ phức tạp thời gian.

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

Trước khi bước vào bài học ngày hôm nay, các em suy nghĩ và trả lờ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

Nội dung 1: Các khái niệm cơ bản

Theo em: Tính hiệu quả của thuật toán dựa trên những tiêu chí nào? 

Video trình bày nội dung:

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

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

Em hãy cho biết: 

- 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ì? 

Video trình bày nội dung:

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

Nội dung 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

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

Video trình bày nội dung:

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

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

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

Video trình bày nội dung:

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

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

Em hãy trình bày các quy tắc khi ước lượng thời gian thực hiện thuật toán.

Video trình bày nội dung:

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.

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.

………..

Nội dung video Bài 5: Đánh giá thuật toán còn nhiều phần rất hấp dẫn và thú vị. Hãy cùng đăng kí để tham gia học bài và củng cố kiến thức thông qua hoạt động luyện tập và vận dụng trong video.