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

BÀI 24: ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

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

• ĐÁNH GIÁ THỜI GIAN CHẠY: Ước lượng thời gian chạy bằng cách tính tổng các đơn vị thời gian của các lệnh đơn. Các lệnh đơn (gán, đọc dữ liệu, phép toán số học/so sánh) được tính là 1 đơn vị thời gian.

• PHÉP TOÁN TÍCH CỰC: Là phép toán được thực hiện nhiều nhất và đóng vai trò chính trong chương trình.

• KÍ HIỆU O-LỚN (BIG-O): Dùng để đánh giá và phân loại độ phức tạp thời gian khi kích thước dữ liệu đầu vào n tăng lên.

  • Định nghĩa: f(n)=O(g(n)) nếu tồn tại hằng số c>0 và n0​ sao cho f(n)≤c⋅g(n) với mọi n≥n0​.

• QUY TẮC TÍNH ĐỘ PHỨC TẠP:

  • Quy tắc cộng: O(f(n)+g(n))=O(max(f(n),g(n))).

  • Quy tắc nhân: O(f(n)⋅g(n))=O(f(n)⋅g(n)).

  • Ví dụ: T(n)=3n2+nlogn=O(max(3n2,nlogn))=O(n2).

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

1. Việc ước lượng thời gian chạy dựa trên tổng số lệnh đơn giúp đánh giá thuật toán mà không cần cài đặt.

2. Vòng lặp for hoặc while được tính thời gian bằng tổng đơn vị thời gian của các bước lặp.

3. Kí hiệu O-lớn phân loại các thuật toán như: O(1) (hằng số), O(n) (tuyến tính), O(n2) (bình phương),....

4. Quy tắc cộng và quy tắc nhân là công cụ cơ bản để đơn giản hóa biểu thức độ phức tạp.

5. Phân tích độ phức tạp thời gian là cơ sở để so sánh và lựa chọn thuật toán tối ưu cho bài toán.

III. BỐ CỤC SLIDE PPTX

• Slide 1: Tiêu đề

  • Tiêu đề: BÀI 24: ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

  • Nội dung: Mục tiêu đánh giá và phân loại thuật toán dựa trên thời gian chạy.

• Slide 2: Đánh giá thời gian chạy

  • Tiêu đề: ƯỚC LƯỢNG THỜI GIAN CHẠY CHƯƠNG TRÌNH

  • Nội dung: Nguyên tắc tính thời gian từ các lệnh đơn và phép toán tích cực.

• Slide 3: Kí hiệu O-lớn

  • Tiêu đề: KHÁI NIỆM ĐỘ PHỨC TẠP O-LỚN

  • Nội dung: Định nghĩa toán học và ý nghĩa của kí hiệu O-lớn khi n tiến tới vô cùng.

• Slide 4: Các bậc độ phức tạp

  • Tiêu đề: PHÂN LOẠI THUẬT TOÁN THEO O-LỚN

  • Nội dung: Danh sách các bậc phổ biến: O(1),O(logn),O(n),O(n2),O(n3),O(2n),O(n!).

• Slide 5: Quy tắc tính độ phức tạp

  • Tiêu đề: CÁC QUY TẮC TÍNH ĐƠN GIẢN

  • Nội dung: Trình bày chi tiết Quy tắc cộng và Quy tắc nhân với hằng số/hàm số.

• Slide 6: Ví dụ thực hành

  • Tiêu đề: VÍ DỤ MINH HỌA

  • Nội dung: Các bài tập áp dụng quy tắc để rút gọn hàm thời gian T(n).

• Slide 7: Tổng kết

  • Tiêu đề: TỔNG KẾT BÀI HỌC

  • Nội dung: Tóm tắt vai trò của phân tích thuật toán trong thiết kế lập trình.