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:

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.

Xác định độ phức tạp thời gian cho chương trình sau:

n = 1000

s = 0

for i in range (n);

   s = s + i*(i+1)

print (s)

Hướng dẫn giải:

- Chương trình trên tính tổng các giá trị i*(i+1) trong khoảng từ 0 đến n-1 và lưu kết quả vào biến s. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng for và các phép toán trong vòng lặp.

- Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1.000. Vậy số lần lặp là n, hay 1.000 lần.

- Các phép toán trong vòng lặp:

 + Phép gán s = s + i*(i+1): Đây là phép gán giá trị vào biến s, có độ phức tạp là O(1).

 + Phép toán i*(i+1): Đây là phép nhân và cộng, có độ phức tạp là O(1).

Vậy tổng độ phức tạp thời gian của chương trình là O(n), hay O(1.000).

Qua bài học này, các em sẽ: 

- Biết cách phân tích độ phức tạp thời gian thuật toán.

- Nhận biết được phép toán tích cực trong chương trình.

- Biết và thực hiện được tính toán độ phức tạp thời gian của một số thuật toán đã biết.

2.1. Trắc nghiệm Bài 24 SGK Tin học 11 Kết nối tri thức  

Như vậy là các em đã xem qua bài giảng Bài 24 Chủ đề 6 Tin học lớp 11 Kết nối tri thức. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24.

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Kết nối tri thức Bài 24 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 111 SGK Tin học 11 Kết nối tri thức - KNTT

Hoạt động 1 trang 112 SGK Tin học 11 Kết nối tri thức - KNTT

Câu hỏi 1 trang 113 SGK Tin học 11 Kết nối tri thức - KNTT

Câu hỏi 2 trang 113 SGK Tin học 11 Kết nối tri thức - KNTT

Hoạt động 2 trang 113 SGK Tin học 11 Kết nối tri thức - KNTT

Câu hỏi trang 114 SGK Tin học 11 Kết nối tri thức - KNTT

Luyện tập 1 trang 114 SGK Tin học 11 Kết nối tri thức - KNTT

Luyện tập 2 trang 114 SGK Tin học 11 Kết nối tri thức - KNTT

Vận dụng 1 trang 114 SGK Tin học 11 Kết nối tri thức - KNTT

Vận dụng 2 trang 114 SGK Tin học 11 Kết nối tri thức - KNTT

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!