Giáo án Bài 25 · KHMT. Thực hành xác định độ phức tạp thời gian thuật toán

Huy động kinh nghiệm về vòng lặp lồng nhau và đặt vấn đề: làm thế nào đếm được số lần thực hiện thân vòng lặp khi số lần phụ thuộc vào i.

GV chiếu đoạn chương trình mẫu với n=6, gồm biến d=0, vòng for i trong range(n), vòng for j trong range(i) và lệnh d+=1 ở thân vòng trong. HS dự đoán giá trị d in ra và giải thích cách dự đoán trong 1 phút.
Câu hỏi GV đặt ra: Với i=0, vòng trong có chạy lần nào không? Với i=3, vòng trong chạy mấy lần? Vậy tổng số lần cộng 1 khi n=6 là bao nhiêu?

Dự đoán ban đầu của HS và đáp số đúng d=15, vì 0+1+2+3+4+5=15. HS nhận ra số lần chạy thân vòng trong phụ thuộc vào i nên phải cộng dồn theo từng giá trị i, không nhân đơn giản n với một số cố định.

HS biết cách thêm bộ đếm vào đúng vị trí của thuật toán, thu thập số liệu với nhiều giá trị n và nhận ra quy luật của dãy số đếm.

HS làm việc theo cặp đôi với Phiếu học tập số 1. Nhiệm vụ gồm ba bước: (1) đặt lệnh d=0 trước vòng lặp và lệnh d+=1 đúng ở thân vòng trong; (2) thay n bằng 1, 2, 3, 4, 5, 6 rồi ghi giá trị d vào bảng; (3) nhận xét quy luật giữa n và d.
Câu hỏi GV đặt ra: Vì sao phải đặt d+=1 ở thân vòng trong mà không đặt ở thân vòng ngoài? Các giá trị d thu được có quan hệ gì với tổng 0+1+…+(n−1)?

Bảng kết quả HS điền đầy đủ: n=1 thì d=0; n=2 thì d=1; n=3 thì d=3; n=4 thì d=6; n=5 thì d=10; n=6 thì d=15. HS nhận xét: d(n) bằng tổng 0+1+…+(n−1) và bằng $\dfrac{n(n-1)}{2}$; mỗi lần n tăng thêm 1 thì d tăng thêm đúng n−1 lượt.

HS giải thích được vì sao $\dfrac{n(n-1)}{2}$ có bậc $O(n^2)$, phân biệt thao tác đếm với thời gian chạy thật và không coi số đo nhỏ là chứng minh bậc.

GV tổ chức thảo luận lớp với ba câu hỏi:
(1) Trong $\dfrac{n(n-1)}{2}$, hạng nào chi phối khi n lớn? Vì sao?
(2) Chạy n=6 được 15 có đủ để kết luận bậc hai không? Vì sao?
(3) Thời gian chạy thật bằng giây có phải là số thao tác đếm không? Vì sao?

Kiến thức HS rút ra: khi n lớn, hạng $n^2$ chi phối nên bậc là $O(n^2)$; số đo với một vài giá trị n nhỏ chỉ là dữ liệu minh hoạ, không phải chứng minh; số thao tác đếm khác với thời gian chạy thật vì thời gian còn phụ thuộc máy tính, ngôn ngữ và điều kiện chạy.

HS vận dụng công thức $\dfrac{n(n-1)}{2}$ để tính số lượt và nhận biết các lỗi thường gặp khi xác định độ phức tạp.

HS làm bài tập 1 đến 6 trong bài học, ưu tiên dùng bài tập tương tác trên NeoEdu để tự kiểm tra ngay.
Bài 1: n=3, in n*(n-1)//2.
Bài 2: n=5, in n*(n-1)//2.
Bài 3: n=8, in n*(n-1)//2.
Bài 4: $\dfrac{n(n-1)}{2}$ có bậc tăng trưởng nào? A. $O(n^2)$; B. $O(n)$; C. $O(1)$; D. $O(\log n)$.
Bài 5: Có một vòng for trong hàm con không tính vào độ phức tạp. Đúng hay sai?
Bài 6: Sắp xếp các bước theo phương pháp giải: thử n nhỏ và ghi kết quả; tổng hợp thành công thức; giải thích bậc chứ không chỉ suy từ giây; thêm bộ đếm đúng vị trí.

Đáp án: bài 1 là 3; bài 2 là 10; bài 3 là 28; bài 4 là A ($O(n^2)$); bài 5 là Sai, vì vòng lặp trong hàm con vẫn phải tính theo số lần hàm được gọi; bài 6 là: thêm bộ đếm đúng vị trí → thử n nhỏ và ghi kết quả → tổng hợp thành công thức → giải thích bậc chứ không chỉ suy từ giây.

HS viết chương trình hoàn chỉnh đếm thao tác, kiểm tra theo dữ liệu mẫu và các ca biên, đồng thời giải thích sự thay đổi số lượt khi n tăng trong bối cảnh thực tế.

Tình huống thực tế: trong một lớp có n học sinh, mỗi cặp học sinh cần được kiểm tra một lần để so sánh bài làm. HS làm hai nhiệm vụ.
(a) Đếm thân vòng tam giác cho n=6, giải thích công thức, viết chương trình Python hoàn chỉnh có bộ đếm, chạy kiểm tra với dữ liệu mẫu và xét thêm n=0.
(b) Nếu n tăng từ 10 lên 20, số đếm theo công thức thay đổi bao nhiêu lần? Giải thích vì sao tỉ số này không đúng bằng 4 khi còn hạng thấp.
Nhiệm vụ (a) làm trên lớp trong phần thời gian còn lại; phần chạy kiểm tra đầy đủ và viết lập luận hoàn chỉnh giao về nhà.

Chương trình HS viết có bộ đếm d khởi tạo bằng 0, hai vòng lồng nhau đúng thứ tự, in ra kết quả 15 khi n=6 và 0 khi n=0. Lập luận: tổng số lượt bằng 0+1+…+(n−1)=$\dfrac{n(n-1)}{2}$, với n=6 cho 15; bậc là $O(n^2)$ vì đây là bậc hai. Với (b): 10×9/2=45; 20×19/2=190; tỉ lệ $190/45 \approx 4{,}22$; không đúng bằng 4 vì còn hạng thấp trong số thao tác thực tế.