Ôn tập kiến thức Tin học 11 định hướng Khoa học máy tính Cánh diều bài 5: Đánh giá thuật toán

[toc:ul]

1. CÁC KHÁI NIỆM CƠ BẢN

- Trong tin học, các thuật toán được đánh giá và so sánh dựa trên tính hiệu quả.

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

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

- Các ngôn ngữ lập trình có lệnh cho phép bấm giờ tính thời gian chạy thực thi chương trình. 

Ví dụ: Python có lệnh time()...

- Cách tính giờ chạy thực thi chương trình cụ thể không áp dụng được khi muốn so sánh hiệu quả để lựa chọn thuật toán vì các vấn đề sau đây:

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

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

- Thời gian thực thi thuật toán phụ thuộc kích thước đầu vào, được đại diện bằng một số tự nhiên n.

Ví dụ: 

+ Dữ liệu đầu vào là dãy gồm 10 số → thời gian chạy mất 1s.

+ Dữ liệu đầu vào là dãy gồm 1000 số → thời gian chạy mất 10s. 

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

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

Ví dụ: Những trường hợp được coi là phép toán sơ cấp:

+ Phép toán số học, phép so sánh… với các toán hạng là giá trị cụ thể.

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

Chú ý: Phép lặp, 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

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

Ví dụ: Cách giải thứ hai của bài toán trong Hoạt động:

    s1 = n + 1

    s2 = n*s1

    s3 = s2/2

→ T(n) = 3. 

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

Ví dụ: Cách giải thứ nhất của bài toán trong Hoạt động:

while i <= n:

  tong = tong + i

  i = i + 1

→ T(n) = n – 1. 

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 

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

Kí pháp O lớ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ì f1(n) × f2(n) = O(g1(n)× g2(n)). 

5. CÁC QUY TẮC KHI ƯỚC LƯỢNG THỜI GIAN THỰC HIỆN THUẬT TOÁ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ụ: