Giáo án tích hợp AI Tin học 11 KHMT Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Xem mẫu

Giáo án điện tử Tin học 11 (Định hướng Khoa học máy tính) Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán. Sách kết nối tri thức mới nhất cho năm học 2026 - 2027. Có tích hợp video AI, điều chỉnh cấu trúc, kiến thức phù hợp với năm học mới để tạo ra một bản powerpoint hoàn thiện và chất lượng. Thầy/cô chỉ cần tải về và giảng dạy. Có thể chỉnh sửa dễ dàng.

BÀI 25: THỰC HÀNH XÁC ĐỊNH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

I. NỘI DUNG CHI TIẾT BÀI HỌC

PHÂN TÍCH THUẬT TOÁN: Để xác định độ phức tạp, ta gọi n là kích thước dữ liệu đầu vào và T(n) là tổng số lệnh cơ bản cần thực hiện trong trường hợp tồi nhất. Sau đó, áp dụng quy tắc O-lớn để tìm bậc độ phức tạp.
VÍ DỤ TÌM KIẾM TUẦN TỰ: Với mảng n phần tử, vòng lặp duyệt tối đa n lần, mỗi lần thực hiện lệnh so sánh. Tổng số phép tính cơ bản là T(n) = n + 1, do đó độ phức tạp là O(n), tức là độ phức tạp tuyến tính.
VÍ DỤ SẮP XẾP CHỌN: Dựa trên cấu trúc vòng lặp lồng nhau, thời gian chạy được biểu diễn bằng tổng các lệnh trong mỗi bước. Kết quả phân tích cho thấy T(n) = n^2 + 3n - 3, suy ra độ phức tạp là O(n^2), tức là độ phức tạp bình phương.

II. KIẾN THỨC TRỌNG TÂM

Phân tích độ phức tạp là kĩ năng quan trọng để đánh giá hiệu quả thuật toán.
Cần xác định trường hợp tồi nhất để ước lượng T(n) một cách chính xác.
Các lệnh gán, so sánh trong vòng lặp được quy đổi thành đơn vị thời gian để tính toán.
Sử dụng quy tắc O-lớn giúp đơn giản hóa biểu thức T(n) phức tạp về dạng bậc cơ bản.
Thuật toán có vòng lặp lồng nhau thường dẫn đến độ phức tạp bậc cao như bình phương O(n^2).

III. BỐ CỤC SLIDE PPTX

Slide 1: Tiêu đề
- Tiêu đề: BÀI 25: THỰC HÀNH XÁC ĐỊNH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
- Nội dung: Mục tiêu rèn luyện kĩ năng phân tích và đánh giá độ phức tạp thuật toán.
Slide 2: Quy trình phân tích
- Tiêu đề: CÁC BƯỚC XÁC ĐỊNH ĐỘ PHỨC TẠP
- Nội dung: Xác định kích thước n, tính tổng phép tính T(n) trong trường hợp tồi nhất, xác định bậc O-lớn.
Slide 3: Tìm kiếm tuần tự
- Tiêu đề: PHÂN TÍCH TÌM KIẾM TUẦN TỰ
- Nội dung: Giải thích tại sao thuật toán có độ phức tạp tuyến tính O(n).
Slide 4: Sắp xếp chọn
- Tiêu đề: PHÂN TÍCH SẮP XẾP CHỌN
- Nội dung: Giải thích quá trình tính toán để đạt độ phức tạp bình phương O(n^2).
Slide 5: Luyện tập
- Tiêu đề: BÀI TẬP CỦNG CỐ
- Nội dung: Xác định độ phức tạp của các thuật toán khác như nổi bọt hoặc các hàm lồng nhau.
Slide 6: Tổng kết
- Tiêu đề: TỔNG KẾT
- Nội dung: Tầm quan trọng của việc đánh giá độ phức tạp trong thiết kế chương trình tối ưu.