Giáo án Khoa học máy tính 11 kết nối Bài 24: Đánh giá độ phức tạp thời gian thuật toán

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV đặt vấn đề theo Hoạt động 1 trang 112 SGK, yêu cầu HS thảo luận nhóm đôi trả lời câu hỏi: Quan sát và thực hiện đánh giá thời gian chạy của các chương trình 1 và 2 trong Hình 24.2. Từ đó biết và hiểu được cách đánh giá thời gian thực hiện chương trình.

- GV cho HS tìm hiểu cách đánh giá, ước lượng giá trị thời gian chạy T(n) của chương trình theo khái niệm đơn vị thời gian - thời gian thực hiện một phép tính đơn trong máy tính.

- GV phân tích cho HS hiểu khái niệm này và cho HS biết rõ cách tính này tuy không chính xác như thời gian thực nhưng hiện nay giới khoa học máy tính chọn để tính thời gian chạy của thuật toán.

- GV lưu ý HS: Trong một chương trình, phép toán được thực hiện nhiều nhất và đóng vai trò chính khi thực hiện 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 thì phép toán tích cực là phép cộng C = C + 1 tại dòng 4. Với chương trình 2 thì phép cộng C = C + 1 tại dòng 6 chính là phép toán tích cực.

- Dựa vào kiến thức vừa tìm hiểu, GV yêu cầu HS trả lời câu hỏi củng cố trang 113 SGK:

1. Các lệnh và đoạn chương trình sau cần chạy trong bao nhiêu đơn vị thời gian?

(a)

1    n = 1000000

2    for k in range (n):

3         if k % 3 == 0:

4             print (k)

(b)

1    n = 1000000

2    b = 3

3    for k in range (0, n, b):

4          print (k)

2. Khẳng định “Trong mọi chương trình chỉ có đúng một phép toán tích cực” là đúng hay sai?

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

- GV quan sát, hướng dẫn (nếu cần).

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- Đại diện nhóm HS trình bày.

*Câu hỏi củng cố tr.113 SGK:

1. (a) T(n) = .        (b) T(n) =  + 1.

2. Khẳng định sai.

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

- GV chốt kiến thức của hoạt động này và chuyển sang hoạt động tiếp theo.

1. Đánh giá thời gian thực hiện chương trình

Cách đánh giá thời gian chạy chương trình được dựa trên một bộ khung các nguyên tắc dùng làm căn cứ để tính toán. Các nguyên tắc khung như sau:

1. Các phép toán đơn giản như phép tính số học + - */ phép lấy thương nguyên và số dư, các phép so sánh sẽ tinh là 1 đơn vị thời gian.

2. Các phép toán lôgic cơ bản như AND, OR, NOT sẽ tính là 1 đơn vị thời gian.

3. Các lệnh đơn như lệnh gán, lệnh in, đọc dữ liệu.... tính là 1 đơn vị thời gian.

4. Vòng lặp for hoặc while sẽ được tính thời gian bằng tổng đơn vị thời gian thực hiện của mỗi bước lặp.

5. Lệnh if với nhiều trường hợp rẽ nhánh sẽ được tính thời gian bằng đơn vì thời gian lớn nhất của các lệnh nhánh.

→ Áp dụng các nguyên tắc tính khung thời gian trên chúng ta có thể tinh được gần chính xác thời gian thực hiện chương trình mà không cần cài đặt và chạy chương trình trên máy tính.

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV đặt vấn đề theo Hoạt động 2 trang 113 SGK, yêu cầu HS thảo luận nhóm đôi: Cùng trao đổi và tìm hiểu cách phân loại thuật toán dựa trên độ phức tạp thời gian thuật toán.

- GV hướng dẫn HS phân tích ví dụ Hình 24.2 dựa trên Định nghĩa kí hiệu O-lớn:

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

Chọn c = 2, n₀ = 3. Khi đó với n ≥ n₀  ta có:

T₁(n) = n + 3 ≤ n + n = c.n.

Do đó T₁(n) = O(n). Chúng ta nói 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) = n² + 3.

Chọn c = 2, n₀ = 2. Khi đó với n ≥ n₀, ta có:

T₂(n) = n² + 3 < n² +  = 2n² = c.n².

Vậy suy ra T₂(n) = O(n²). Ta nói chương trình 2 ở trên có độ phức tạp thời gian O(n²) - bình phương.

- GV yêu cầu các nhóm thảo luận trả lời câu hỏi Củng cố tr.114: Tính độ phức tạp của các hàm thời gian sau:

a) T(n) = 2n(n – 2) + 4.

b) T(n) = n³ + 5n – 3.

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- GV mời 1 - 2 nhóm trình bày kết quả thảo luận

* Câu hỏi củng cố tr.114 SGK:

a) T(n) = O(n²).

b) T(n) = O(n³).

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

- GV tóm tắt một vài ý quan trọng:

+ Các hàm thời gian T(n) của các thuật toán đều có giá trị tăng rất lớn khi n tăng đến vô cùng.

→ Cần có cách phân loại các “bậc” hay “độ tăng của các hàm thời gian này.

+ Trong khoa học máy tính, người ta định nghĩa khái niệm bậc để so sánh mức tăng của thời gian.

Giả sử cho trước hai hàm thời gian f(n) và g(n), khi đó nếu khi n tăng lên vô hạn nhưng mức tăng của f(n) không vượt quá C.g(n) với C là hằng số nào đó thì chúng ta nói f(n) có bậc g(n) và dùng kí hiệu f(n) = O(g(n)).

→ Kí hiệu f = O(g) sẽ có nghĩa f có độ phức tạp không vượt quá g hay f có bậc g.

+ Trên thực tế người ta sử dụng một số hàm chuẩn để so sánh bậc như 1 - hằng số, logn - logarit, n - tuyến tính, nlogn - tuyến tính logarit, n² - bình phương, n^k - đa thức, aⁿ - lũy thừa, n! - giai thừa.

+ Các thuật toán với độ phức tạp thời gian từ bậc đa thức trở xuống được gọi là các thuật toán tốt. Các thuật toán ở các mức còn lại sẽ coi là khó.

+ Hình bên mô tả các độ tăng của các hàm chuẩn.

- GV chốt kiến thức và chuyển sang hoạt động tiếp theo.

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

- Kí hiệu O-lớn dùng để đánh giá và phân loại độ phức tạp thời gian của thuật toán khi kích thước đầu vào của bài toán tăng lên vô cùng.

- Định nghĩa O-lớn (big-O):

Cho f(n) và g(n) là hai hàm có đối số tự nhiên. Ta viết 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 n₀ ≥ 1 sao cho với mọi n ≥ n₀ ta có f(n) ≤ c.g(n). Nếu f(n) là O-lớn của g(n) thì có thể viết f(n) = O(g(n)).

- Các thuật toán sẽ được đánh giá qua độ phức tạp của một số hàm chuẩn như:

O(1) - hằng số

O(logn) - logarit

O(n) - tuyến tính

O(nlogn) - tuyến tính logarit

O(n²) - bình phương

O(n^k) - đa thức

O(aⁿ) - lũy thừa

O(n!) - giai thừa.