Giáo án NLS Tin học 11 KHMT kết nối Bài 24: Đánh giá độ phức tạp thời gian thuật toán
Giáo án NLS Tin học 11 (Khoa học máy tính) kết nối tri thức Bài 24: Đánh giá độ phức tạp thời gian thuật toán. Với năng lực số được tích hợp, tiết học sẽ giúp học sinh làm quen và ứng dụng công nghệ, tin học. KHBD này là file word, tải về dễ dàng. Là mẫu giáo án mới nhất năm 2026 để giáo viên dạy tốt môn Tin học 11.
Xem: => Giáo án tích hợp NLS Tin học 11 Khoa học máy tính Kết nối tri thức
Ngày soạn: .../.../...
Ngày dạy: .../.../...
BÀI 24: ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
I. MỤC TIÊU
1. Kiến thức
Học xong bài này, HS đạt các yêu cầu sau:
- 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.
- Tính và ước lượng được thời gian thuật toán và chương trình.
- Tính được độ phức tạp thời gian thuật toán.
2. Năng lực
Năng lực chung:
- Tự chủ và tự học: biết lắng nghe, tự giác học tập và hoàn thành nhiệm vụ; tích cực tham gia các hoạt động học tập trong lớp.
- Giao tiếp và hợp tác: có thói quen trao đổi, giúp đỡ nhau trong học tập; biết cùng nhau hoàn thành nhiệm vụ học tập theo sự hướng dẫn của GV.
- Giải quyết vấn đề và sáng tạo: ứng dụng các kiến thức đã học vào thực tế, phát triển khả năng giải quyết vấn đề có tính tích hợp liên môn giữa Tin học với các môn học khác.
Năng lực riêng:
- 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.
- Tính và ước lượng được thời gian thuật toán và chương trình.
- Tính được độ phức tạp thời gian thuật toán.
Năng lực số:
- 5.2.NC1b: Sử dụng môi trường lập trình để đo thời gian thực thi thực tế, sử dụng công cụ vẽ đồ thị để trực quan hóa tốc độ tăng trưởng của hàm.
- 6.2.NC1b: Sử dụng AI để phân tích đoạn mã và giải thích độ phức tạp, hoặc sinh ra các đoạn mã mẫu theo độ phức tạp yêu cầu.
- 1.2.NC1a: Phân tích sự khác biệt giữa thời gian lý thuyết và thời gian thực chạy trên máy tính.
- 6.1.NC1a: Hiểu mối quan hệ giữa kích thước dữ liệu đầu vào và tài nguyên thời gian tiêu tốn.
3. Phẩm chất
- Trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
1. Đối với GV
- SGK, tài liệu giảng dạy, giáo án PPT.
- Phòng thực hành máy tính kết nối Internet.
- Máy chiếu.
- Video AI tạo bằng công cụ AI được dùng để khởi động bài học.
2. Đối với HS
- SGK, SBT Tin học 11, vở ghi chép.
III. TIẾN TRÌNH DẠY HỌC
1. HOẠT ĐỘNG KHỞI ĐỘNG
a) Mục tiêu: GV khơi gợi sự tò mò của HS đến việc đánh giá tính tối ưu, hiệu quả của chương trình.
b) Nội dung: GV tổ chức trả lời câu hỏi ở phần Mở đầu, thông qua đó tiếp cận đến khái niệm Độ phức tạp thời gian thuật toán và khái niệm “bậc” của độ phức tạp .
c) Sản phẩm: Dựa vào kiến thức của bản thân, HS thực hiện yêu cầu GV đưa ra.
d) Tổ chức thực hiện:
Bước 1: GV chuyển giao nhiệm vụ:
- GV yêu cầu xem video AI được thiết kế để phục vụ bài dạy và trả lời câu hỏi xuất hiện trong video đó.
- GV dẫn dắt, đặt vấn đề cho HS: Quan sát Hình 24.1, chúng ta dễ thấy phép nhân hai số có n chữ số sẽ cần n2 phép nhân và 2n phép cộng, vậy tổng số các phép tính đơn của phép nhân này là n2 + 2n, chúng ta nói độ phức tạp thời gian của phép nhân này có bậc m2.
Năm 1960, trong một tiết dạy về công nghệ thông tin, nhà toán học Nga, Viện sĩ Kolmogorov đã hỏi các sinh viên của mình là có ai tìm được cách tính phép nhân trên với thời gian tốt hơn bậc n2 được không? Khi đó đây là một bài toán chưa có lời giải. Đúng một tuần sau, một sinh viên tên là Karatsuba đã đưa cho Viện sĩ Kolmogorov một lời giải tốt hơn về phép tính nhân trên chỉ với độ phức tạp thời gian bậc n1,58496.
Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao?
Chương trình 1 Chương trình 2
1 n = 100 1 n = 100
2 C = 0 2 C = 0
3 for k in range (n): 3 for i in range (n):
4 C = C + 1 4 for j in range (n):
5 print (C) 5 C = C + 1
6 print (C)
Hình 24.2
Bước 2: HS thực hiện nhiệm vụ học tập:
- HS xem video và suy nghĩ câu trả lời.
- HS lắng nghe, suy nghĩ câu trả lời.
Bước 3: Báo cáo kết quả hoạt động, thảo luận:
- GV gọi đại diện một số HS trả lời.
Gợi ý: Chương trình 1 chạy nhanh hơn vì chương trình 1 có 1 vòng lặp, chương trình 2 có 2 vòng lặp.
- HS khác nhận xét, bổ sung.
Bước 4: Đánh giá kết quả thực hiện:
- GV nhận xét, đánh giá và kết luận.
[6.1.NC1a: HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản.
2.1.NC1a: HS thực hiện các tương tác cơ bản với học liệu số (xem video, trả lời câu hỏi trên môi trường số).
1.1.NC1a: HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV.]
- GV nhận xét câu trả lời của HS. Trên cơ sở đó, GV dẫn dắt HS vào bài học mới: Trong bài học trước, chúng ta đã được làm quen với khái niệm Độ phức tạp thời gian của thuật toán, được xác định là thời gian thực hiện chương trình/thuật toán. Thời gian này phụ thuộc vào khối lượng của dữ liệu cần phải lưu trữ trong quá trình thực hiện chương trình/thuật toán, đặc biệt liên quan tới các bước giải quyết một vấn đề cụ thể đưa ra trong chương trình thuật toán. Vậy căn cứ vào đâu để đánh giá thời gian thực hiện của một chương trình? Để tìm ra câu trả lời chính xác nhất trong câu hỏi Khởi động trên, chúng ta cùng vào - Bài 24: Đánh giá độ phức tạp thời gian thuật toán.
2. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC
Hoạt động 1: Tìm hiểu về đánh giá thời gian thực hiện chương trình
a) Mục tiêu:
- HS biết và hiểu cách đánh giá (ước lượng) gần đúng thời gian chạy của thuật toán và chương trình.
- HS biết được khái niệm phép toán tích cực trong quá trình đánh giá.
b) Nội dung: GV đặt vấn đề, HS tìm hiểu thông tin mục 1 trang 111 - 113 SGK và thực hiện nhiệm vụ được giao.
c) Sản phẩm: Đánh giá thời gian thực hiện chương trình.
d) Tổ chức thực hiện:
…………………………………………..
…………………………………………..
…………………………………………..
Hoạt động 2: Tìm hiểu về phân tích độ phức tạp thời gian thuật toán
a) Mục tiêu: Giúp HS biết được ý nghĩa và cách phân loại thời gian thuật toán theo các bậc của các hàm thông qua kí hiệu O-lớn.
b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và nêu được cách phân loại thời gian thuật toán theo các bậc của các hàm thông qua kí hiệu O-lớn.
c) Sản phẩm: Phân tích độ phức tạp thời gian thuật toán.
d) Tổ chức thực hiện:
| HOẠT ĐỘNG CỦA GV VÀ HS | SẢN PHẨM DỰ KIẾN | NLS |
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 yêu cầu HS: Sử dụng AI tìm hiểu: + Kí hiệu O-lớn (big-O) + Độ phức tạp của một số hàm dùng để đánh giá 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 T1(n) = n + 3. Chọn c = 2, n0 = 3. Khi đó với n ≥ n0 ta có: T1(n) = n + 3 ≤ n + n = c.n. Do đó T1(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 T2(n) = n2 + 3. Chọn c = 2, n0 = 2. Khi đó với n ≥ n0, ta có: T2(n) = n2 + 3 < n2 + Vậy suy ra T2(n) = O(n2). Ta nói chương trình 2 ở trên có độ phức tạp thời gian O(n2) - 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) = n3 + 5n – 3. Bước 2: HS thực hiện nhiệm vụ học tập: - HS sử dụng AI tìm hiểu kiến thức. - 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: - HS đọc kết quả từ AI, đối chiếu với SGK và rút ra kết 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(n2). b) T(n) = O(n3). - 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, n2 - bình phương, nk - đa thức, an - 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 n0 ≥ 1 sao cho với mọi n ≥ n0 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(n2) - bình phương O(nk) - đa thức O(an) - lũy thừa O(n!) - giai thừa. | - 6.2.NC1a: Sử dụng AI để tìm kiếm thông tin phục vụ học tập. - 1.2.NC1a: HS tính được độ phức tạp của các hàm thời gian. |
Hoạt động 3: Tìm hiểu về một số quy tắc thực hành tính độ phức tạp thời gian thuật toán
a) Mục tiêu: Giúp HS biết và thực hành được cách tính độ phức tạp thời gian thuật toán dựa trên một số quy tắc đơn giản.
b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và nêu được một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán.
c) Sản phẩm: Một số quy tắc thực hành tính độ phức tạp thời gian thuật toán.
d) Tổ chức thực hiện:
…………………………………………..
…………………………………………..
…………………………………………..
3. HOẠT ĐỘNG LUYỆN TẬP
a) Mục tiêu: HS củng cố kiến thức về đánh giá độ phức tạp thời gian thuật toán.
b) Nội dung: HS trả lời câu hỏi trắc nghiệm và hoàn thành bài tập phần Luyện tập SGK trang 114.
c) Sản phẩm học tập: HS trả lời câu hỏi về đánh giá độ phức tạp thời gian thuật toán.
d) Tổ chức thực hiện:
Bước 1: GV chuyển giao nhiệm vụ:
- GV tổ chức trò chơi trắc nghiệm nhanh trên Quizizz hoặc Kahoot để củng cố toàn bài.
- GV cung cấp mã QR hoặc đường Links cho HS làm Phiếu bài tập, trả lời nhanh một số câu hỏi trắc nghiệm tổng kết bài học.
Câu 1: Giả sử một chương trình P mô tả một thuật toán nào đó. Người ta đo được các thông tin thời gian sau:
T1 = thời gian chương trình nhập dữ liệu input và đưa vào bộ nhớ.
T2 = thời gian chạy chương trình từ khi nhập xong dữ liệu input và tính xong dữ liệu output.
T3 = thời gian đưa dữ liệu output ra thiết bị ngoài chuẩn.
Khi đó thời gian chạy chương trình T(n) dùng để tính độ phức tạp thời gian của thuật toán là phương án nào trong các phương án sau?
A. T1 + T2. B. T2. C. T2 + T3. D. T1 + T2 + T3.
Câu 2: Cho chương trình sau:
1 <input n - số tự nhiên dương>
2 S = 0
3 for i in range(1, n + 1):
4 S = S + i*i
5 print(S)
Kết quả đánh giá thời gian chạy chương trình T(n) là
A. n + 2. B. 2n. C. n2. D. log2n.
Câu 3: Độ phức tạp của hàm n + 2n.log2(n) + 10 theo kí hiệu O-lớn là
A. n. B. 2n. C. nlog2n. D. nlogn.
Câu 4: Độ phức tạp của hàm 2n2 + 3n3log5(n) + n3/2 theo kí hiệu O-lớn là
A. 2n2. B. 2n2 + n3.logn. C. n3.logn. D. n3/2.
Câu 5: Độ phức tạp của hàm 2n + 3n + 5n theo kí hiệu O-lớn là
A. 2n. B. 3n. C. 4n. D. 5n.
- GV tổ chức cho HS làm bài tập phần Luyện tập trang 114 SGK:
Bài 1. Xác định độ phức tạp thời gian tính toán cho chương trình sau:
1 n = 1000
2 S = 0
3 for i in range (n):
4 S = S + i(i+1)
5 print(S)
Bài 2. Xác định độ phức tạp thời gian tính toán cho chương trình sau:
1 n = 1000
2 Sum=0
3 i = 1
4 while i < n:
5 i = i*2
6 Sum = Sum + i
7 print(Sum)
Bước 2: HS thực hiện nhiệm vụ học tập:
- HS suy nghĩ, hoàn thành các bài tập GV yêu cầu.
- GV quan sát và hỗ trợ, hướng dẫn.
Bước 3: Báo cáo kết quả hoạt động, thảo luận:
- HS xung phong báo cáo bài tập mình làm.
- Các HS khác nhận xét, bổ sung bài làm của bạn.
Gợi ý trả lời:
| Câu 1 | Câu 2 | Câu 3 | Câu 4 | Câu 5 |
| B | A | D | C | D |
[2.1.NC1a: HS thực hiện các tương tác được xác định rõ ràng với công nghệ số (làm bài tập online) trong lớp học.]
Bài 1. T(n) = 2n + 2 = O(n).
Bài 2. T(n) = 2log2n + 2 = O(logn).
[1.2.NC1a: HS tính được độ phức tạp thời gian tính toán cho chương trình.]
Bước 4: Đánh giá kết quả thực hiện:
- GV chữa bài, chốt đáp án, tuyên dương các hoạt động tốt, nhanh và chính xác.
4. HOẠT ĐỘNG VẬN DỤNG
…………………………………………..
…………………………………………..
…………………………………………..
=> 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