Giáo án Bài 24 · KHMT. Đánh giá độ phức tạp thời gian thuật toán

HS nhận ra cần đo tốc độ thuật toán bằng số thao tác theo kích thước đầu vào, không chỉ bằng số dòng mã hay thời gian chạy trên một máy cụ thể.

GV trình chiếu hai đoạn mã: đoạn A có một vòng lặp chạy $n$ lần; đoạn B có hai vòng lặp lồng nhau, mỗi vòng chạy $n$ lần. GV hỏi: Nếu $n=5$ rồi $n=50$, đoạn nào tăng số thao tác nhanh hơn? Dự đoán số thao tác của mỗi đoạn khi $n=5$ và $n=50$ rồi ghi vào vở. Sau đó HS chạy thử đoạn B với $n=5$ để kiểm tra dự đoán.

Bảng dự đoán của HS: đoạn A thực hiện $5$ thao tác khi $n=5$ và $50$ thao tác khi $n=50$; đoạn B thực hiện $25$ thao tác khi $n=5$ và $2500$ thao tác khi $n=50$. Kết luận ban đầu: số thao tác của đoạn B tăng nhanh hơn nhiều khi $n$ lớn, nên cần đo theo kích thước đầu vào thay vì đo theo giây.

HS giải thích được ý nghĩa của bậc $O(n)$ và $O(n^2)$, nhận biết cấu trúc một vòng và hai vòng lồng nhau, và đếm được số thao tác chính của chương trình Python.

HS làm theo nhóm 4 với Phiếu học tập số 1. HS chạy chương trình mẫu (một vòng với $n=7$; hai vòng lồng nhau với $n=4$; hai vòng lồng nhau với $n=5$ và thay đổi $n$ để quan sát). Nhóm ghi kết quả đếm, trả lời câu hỏi về mối liên hệ giữa cấu trúc vòng lặp và bậc tăng trưởng. Sau khi nhóm hoàn thành, GV dùng chương trình mẫu để kiểm chứng.

Kết quả trong Phiếu học tập số 1: chương trình một vòng với $n=7$ in ra $7$; hai vòng lồng nhau $n\times n$ với $n=4$ in ra $16$ và với $n=5$ in ra $25$. Kết luận HS rút ra: một vòng lặp chạy $n$ lần cho bậc $O(n)$; hai vòng lồng nhau mỗi vòng $n$ lần cho bậc $O(n^2)$; khi $n$ tăng gấp đôi, số thao tác của hai vòng lồng nhau tăng gấp bốn.

HS phân biệt được trường hợp tốt nhất và trường hợp xấu nhất, giải thích được vì sao bỏ hằng số khi phân loại bậc, và nhận biết thuật toán chia đôi có bậc $O(\log n)$.

HS làm theo cặp đôi với Phiếu học tập số 2. Nhiệm vụ gồm: (1) tìm một giá trị $x$ trong dãy $n$ phần tử bằng cách duyệt từ đầu đến cuối, xác định số lần so sánh trong trường hợp tốt nhất và trường hợp xấu nhất; (2) phân loại bậc của $T(n)=3n+2$; (3) chạy chương trình đếm số lần chia đôi $n$ cho đến khi bằng $1$ với $n=8$ và $n=16$, rồi rút ra bậc của thuật toán chia đôi.

Kết quả trong Phiếu học tập số 2: tìm kiếm tuyến tính có trường hợp tốt nhất là $1$ lần so sánh (giá trị nằm đầu dãy) và trường hợp xấu nhất là $n$ lần so sánh (giá trị nằm cuối dãy hoặc không có trong dãy). $T(n)=3n+2$ thuộc $O(n)$ vì bỏ hằng số và hệ số. Chia đôi $8$ xuống $1$ cần $3$ bước, $16$ xuống $1$ cần $4$ bước, nên số bước tăng theo $\log_2 n$, thuộc $O(\log n)$ khi dãy đã sắp xếp.

HS vận dụng quy trình đếm thao tác và phân loại bậc để làm đúng các bài tập cơ bản, đồng thời tự kiểm tra đáp án.

Các nhóm thi đua theo hình thức đội chơi: GV đọc hoặc chiếu lần lượt bài 1 đến bài 6, nhóm giơ bảng đáp án. Sau đó HS làm bài 8 trên giấy và trình bày bằng lời. Có thể tham khảo bài tập tương tác trên trang NeoEdu để tự luyện thêm.

Đáp án: Bài 1: $7$. Bài 2: $16$. Bài 3: $6$ (vì $0+1+2+3=6$). Bài 4: đáp án A, $O(n)$ vì hệ số và hằng số không làm đổi bậc tuyến tính. Bài 5: Sai, vì $O(n)$ là bậc tăng trưởng, không phải đơn vị thời gian thực. Bài 6: chọn kích thước $n$, đếm thao tác chính, viết hàm số đếm, xác định bậc tăng trưởng và trường hợp. Bài 8: Không; hai vòng nối tiếp mỗi vòng $n$ có $2n$ thao tác và thuộc $O(n)$, còn hai vòng lồng nhau $n\times n$ có $n^2$ thao tác và thuộc $O(n^2)$; với $n=5$ là $10$ và $25$.

HS vận dụng kiến thức về bậc thời gian để ước lượng và lựa chọn thuật toán tìm kiếm phù hợp với dữ liệu thực tế, đồng thời kiểm tra điều kiện áp dụng của thuật toán chia đôi.

Tình huống: danh bạ điện thoại có $1000$ người. Cách A: duyệt từ đầu đến cuối để tìm tên. Cách B: nếu danh bạ đã sắp theo tên thì chia đôi để tìm. HS tính số thao tác trong trường hợp xấu nhất của cả hai cách. Sau đó HS viết chương trình đếm tuyến tính với $n=5$ để kiểm tra mã nguồn như bài 7 trong bài tập (đếm hai vòng $n\times n$ với $n=5$ in ra $25$), rồi trả lời câu hỏi: Vì sao không được chia đôi nếu danh bạ chưa sắp theo tên?

Kết quả HS rút ra: cách A trong trường hợp xấu nhất cần khoảng $1000$ lần so sánh, thuộc $O(n)$; cách B cần khoảng $10$ lần chia đôi ($\log_2 1000 \approx 9{,}97$), thuộc $O(\log n)$. Điều kiện áp dụng: chỉ chia đôi được khi dãy đã sắp theo tên, nếu không kết quả có thể sai. Bài 7 (hai vòng $n\times n$ với $n=5$) in ra $25$, mã đúng là hai vòng lồng nhau với biến đếm $d$; kết quả bậc $O(n^2)$, không phải giây.