Lý thuyết Tin học 11 (Cánh diều) Bài 5: Đánh giá thuật toán

Lý thuyết Tin học 11 Bài 5: Đánh giá thuật toán

A. Lý thuyết Đánh giá thuật toán

1. Các khái niệm cơ bản

- Đánh giá thuật toán trong Tin học dựa trên tính hiệu quả.

- Thuật toán hiệu quả là khi thời gian thực hiện và lượng bộ nhớ cần dùng ít hơn.

- Tính ngắn gọn, dễ hiểu và dễ lập trình không phải là tiêu chuẩn quan trọng nhất.

a) Ước lượng thời gian thực thi chương trình và hiệu quả thời gian của thuật toán

- Python có lệnh time() để bẩm giờ tính thời gian thực thi chương trình. Tuy nhiên, cách tính này không áp dụng được để so sánh hiệu quả thuật toán vì những vấn đề sau: 

- Phải lập trình và chạy thử 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.

- Không khả thi để tính thời gian trung bình cho nhiều chương trình khác nhau.

b) Kích thước đầu vào

- Thời gian chạy chương trình phụ thuộc vào kích thước dữ liệu đầu vào (đại diện bằng số tự nhiên n).

- Kích thước dữ liệu đầu vào ảnh hưởng đến thời gian chạy của chương trình.

- Ví dụ, trong bài toán tìm kiếm số hay sắp xếp dãy số, kích thước đầu vào n là độ dài của dãy số.

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

- Thời gian chạy chương trình với đầu vào kích thước n là hàm số T(n) của n.

- Độ phức tạp thời gian ước lượng thời gian thực hiện thuật toán dựa trên số phép toán cần thiết để thực hiện thuật toán với kích thước đầu vào n.

- Tuy nhiên, tính toán số phép toán này không dễ dàng vì khó xác định tương ứng số các phép toán bit với mỗi phép toán và các phép toán số học cũng có thể đếm là nhiều phép toán.

- Trong phân tích thuật toán, phân biệt phép toán sơ cấp và phần còn lại không sơ cấp.

- Một phép toán sơ cấp có thời gian thực hiện không phụ thuộc vào kích thước đầu vào.

- Các phép toán số học, phép so sánh và các hàm toán học với đầu vào giá trị cụ thể được xem là phép toán sơ cấp.

- Phép lặp và phép lựa chọn không phải là phép toán sơ cấp.

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

a) Độ phức tạp thời gian hằng số

- Thuật toán có độ phức tạp thời gian hằng số không phụ thuộc vào kích thước đầu vào.

- Ví dụ, thuật toán tính tổng với chỉ 3 phép toán là một thuật toán hằng số.

- Nhà toán học Friedrich Gauss đã đưa ra cách giải này khi còn là học sinh phổ thông.

b) Độ phức tạp thời gian tuyến tính

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

- Ví dụ, cách giải đầu tiên trong hoạt động trên là một thuật toán tuyến tính vì số phép toán cần thực hiện là T(n) = n - 1.

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

a) Cách ước lượng làm già thêm

- Số phép toán cần thiết để thực hiện thuật toán phụ thuộc vào trường hợp dễ hoặc khó của bài toán, không chỉ phụ thuộc vào kích thước đầu vào.

- Ví dụ, trong thuật toán tìm số lớn nhất trong dãy số, số phép toán cần thiết phụ thuộc vào dãy số đầu vào. Nếu dãy số ban đầu là tăng chặt, thì số phép toán cần thiết là nhiều nhất. Nếu phần tử đầu tiên của dãy là số lớn nhất, thì số phép toán cần thiết là ít nhất.

- Có thể xét ba trường hợp trong việc đánh giá độ phức tạp của thuật toán: trường hợp thuận lợi nhất, trường hợp bất lợi nhất và trường hợp ngẫu nhiên.

- Tuy nhiên, để đưa ra ước lượng trung bình, không dễ tìm ra phương pháp chính xác. Thay vào đó, người ta thường sử dụng cách ước lượng làm già thêm để đảm bảo rằng trong thực tế, không có trường hợp nào vượt quá ước lượng đã đưa ra.

b) Kí pháp O lớn

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

- Thuật toán có độ phức tạp thời gian là tuyến tính nếu số phép toán sơ cấp cần thực hiện không vượt quá một hàm tuyến tính của n. Kí hiệu T(n) = O(n).

- Bảng 1 dưới đây là một số kí hiệu O lớn về thời gian thực hiện thuật toán thường gặp:

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

+ Công thức 1: Nếu f(n)= O(g1(n)) và f2(n) = O(g2(n)) thì f1 (n) + f2 (n)= O(max(g1 (n), g2 (n))). Công thức áp dụng cho hai cấu trúc điều khiển được thực hiện tuần tự.

+ Công thức 2: Nếu f1(n) = O(g1 (n)) và f2(n)= O(g2 (n)) thì f1 (n) x f2 (n)=O(g1 (n) x g2 (n). Công thức áp dụng cho hai cấu trúc điều khiển lồng nhau.

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

a) Quy tắc chung

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

- Mô tả thuật toán sử dụng ba cấu trúc: tuần tự, rẽ nhánh, lặp. Cấu trúc tuần tự gồm phép toán sơ cấp và không sơ cấp. Cấu trúc rẽ nhánh và lặp có thể chứa các dãy phép toán tuần tự. Cần ước lượng số phép toán từ bên trong trở ra ngoài.

b) Lời gọi hàm

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

- Đối với lời gọi hàm với đầu vào là giá trị cụ thể không phụ thuộc n, độ phức tạp thời gian là O(1).

- Đối với các trường hợp khác, độ phức tạp thời gian được ước lượng như một thuật toán.

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

- Cấu trúc tuần 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).

- Ngược 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 các phép toán trong dãy.

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

- Máy tính thực thi cấu trúc rẽ nhánh (hai nhánh hoặc nhiều nhánh) kiểm tra điều kiện và thực hiện một trong các nhánh.

- Kiểm tra điều kiện là tính giá trị biểu thức logic (bao gồm biểu thức số học và phép so sánh), độ phức tạp thời gian là 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 của các nhánh.

- Độ phức tạp thời gian của việc kiểm tra điều kiện trong cấu trúc rẽ nhánh có thể không còn là O(1).

- Nếu như chưa biết trước, việc kiểm tra dãy có phải là cấp số cộng hay không sẽ cần thời gian O(n). 

- Độ phức tạp thời gian của cấu trúc rẽ nhánh trong Hình 1 là O(n) trong mọi trường hợp.

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

- Máy tính thực hiện cấu trúc vòng lặp sẽ kiểm tra điều kiện và thực hiện thân vòng lặp (bao gồm các phép toán tuần tự, phép lựa chọn hay phép lặp khác).

- Thời gian thực hiện cấu trúc vòng lặp 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ụ: độ phức tạp thời gian của thuật toán tìm giá trị cực tiểu một dãy số a1, a2, a3,..., an là O(n).

B. Bài tập Đánh giá thuật toán

Đang cập nhật…

Xem thêm các bài lý thuyết Tin học 11 sách Cánh diều hay, chi tiết tại:

Lý thuyết Bài 6: Kiểm thử và sửa lỗi chương trình

Lý thuyết Bài 7: Lập trình giải bài toán tìm kiếm

Lý thuyết Bài 8: Lập trình một số thuật toán sắp xếp

Lý thuyết Bài 9: Lập trình thuật toán sắp xếp nhanh

Lý thuyết Bài 10: Thiết kế và chương trình từ trên xuống và phương pháp Mô đun hóa