Tin học 11 Kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán

- Không cần cài đặt và chạy chương trình.

- Tính tổng thời gian các phép tính đơn và các lệnh đơn của chương trình.

- Không chính xác hoàn toàn như thời gian thực.

- Dùng để so sánh và ước lượng thời gian chạy chương trình khá chính xác.

- Coi tất cả các lệnh đơn và các phép tính đơn có thời gian chạy như nhau, được gọi là một đơn vị thời gian.

- Đơn giản hoá cách phân tích thời gian tính toán và bảo đảm độ chính xác của tính toán.

 

Chương trình 1: Gọi T₁ là thời gian chạy của chương trình này.

 - Lệnh tại dòng 1 và 2 cần 1 đơn vị thời gian.

 - Vòng lặp tại dòng 3 có n bước lặp, mỗi bước của vòng lặp sẽ thực hiện lệnh tại dòng 4, lệnh này cần 1 đơn vị thời gian.

 - Tổng thời gian của vòng lặp 3 là n thời gian.

 - Lệnh cuối tại dòng 5 cần 1 đơn vị thời gian.

 - T₁ = T₁(n) = n + 3 đơn vị thời gian.

 

Chương trình 2: Gọi T₂ là thời gian chạy của chương trình này.

 - Lệnh tại dòng 1 và 2 cần 1 đơn vị thời gian.

 - Hai vòng lặp lồng nhau tại dòng 3, 4 có n² bước lặp. Mỗi bước lặp sẽ thực hiện lệnh tại dòng 5, lệnh này cần 1 đơn vị thời gian.

 - Tổng thời gian của vòng lặp 3, 4 là n² đơn vị thời gian.

 - Lệnh cuối tại dòng 6 cần 1 đơn vị thời gian.

 - T₂ = T₂(n) = n² + 3 đơn vị thời gian.

 

Lưu ý: Về phép toán tích cực trong chương trình.

 - Phép toán được thực hiện nhiều nhất và đóng vai trò chính khi tính thời gian, được gọi là phép toán tích cực.

 - Ví dụ trong chương trình 1, phép cộng C = C + 1 tại dòng 4 là phép toán tích cực.

 - Trong chương trình 2, phép cộng C = C + 1 tại dòng 6 là phép toán tích cực.

 

- Độ phức tạp thời gian của thuật toán là khối lượng thời gian cần thiết để chạy chương trình thể hiện thuật toán.

- Phân loại thuật toán dựa trên ước lượng độ phức tạp thời gian.

- Độ phức tạp thời gian có thể coi là một hàm số T(n) với n là số tự nhiên đại diện cho dữ liệu đầu vào.

- Giá trị của T(n) được xác định trên cơ sở số lượng phép toán/câu lệnh cần thực hiện trong chương trình/thuật toán.

- Kí hiệu O-lớn được sử dụng để so sánh và phân tích bậc của hàm thời gian T(n) khi n tiến tới vô cùng.

- Ví dụ: chương trình 1 có độ phức tạp thời gian bậc n, viết là T₁(n) = O(n); chương trình 2 có độ phức tạp thời gian bậc n², viết là T₂(n) = O(n²).

 

Định nghĩa kí hiệu O-lớn:

- f(n) và g(n) là hai hàm có đối số tự nhiên.  - f(n) = O(g(n)) và nói f(n) có bậc O-lớn của g(n) nếu tồn tại hằng số c > 0 và số tự nhiên n0 > 1 sao cho với mọi n > n0, f(n) < c.g(n).  - Khi f(n) là O-lớn của g(n) thì có thể viết: f(n) = O(g(n)).

 

Ví dụ về độ phức tạp thời gian của hai chương trình:

 - Chương trình 1 ở Hình 24.2 có hàm thời gian T₁(n) = n + 3.

 - Chọn c = 2, n0 = 3. Khi n > n₀, ta có: T₁(n) = n + 3 < n + n = c.n. Do đó, T₁(n) = O(n). Chương trình 1 có độ phức tạp thời gian O(n) - tuyến tính.

 - Chương trình 2 ở Hình 24.2 có hàm thời gian T₂(n) = n2 + 3.

 - Chọn c = 2, n₀ = 2. Khi n > n0, ta có: T₂(n) = n² + 3 < n² + n₀² < n² + n² = 2n² = c.n². Suy ra T₂(n) = O(n²). Chương trình 2 có độ phức tạp thời gian O(n²) - bình phương.

 

Quy tắc tính đơn giản độ phức tạp thời gian thuật toán:

 - QT1. Quy tắc cộng: O(f(n) + g(n)) = O(max(f(n), g(n))). Áp dụng khi tính độ phức tạp thời gian cho hai chương trình được thực hiện nối tiếp nhau.

 - QT2. Quy tắc nhân: Phép nhân với hằng số: O(C.f(n)) = O(f(n)), với C là hằng số bất kì. Phép nhân với hàm số: O(f(n)g(n)) = O(f(n).O(g(n))). Áp dụng tính độ phức tạp thời gian cho chương trình có hai vòng lặp lồng nhau.