Slide bài giảng Khoa học máy tính 11 kết nối Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tóm lược nội dung

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

KHỞI ĐỘNG

- GV dẫn dắt, đặt vấn đề cho HS: Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình. 

- GV đặt câu hỏi yêu cầu HS trả lời: Các quy tắc đơn giản tính độ phức tạp thời gian mạng lại điều khi khi đánh giá thuật toán?

NỘI DUNG BÀI HỌC GỒM

• Thực hành

• Luyện tập

• Vận dụng

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Xác định độ phức tạp thời gian của thuật toán tìm kiếm tuần tự được thể hiện qua chương trình dưới đây:

1  def LinearSearch(A,K):

2      for i in range(len(A)):

3          if A[i] == K: 

4             return i

5      return -1

Nội dung gợi ý:

Bước 1. Phân tích thời gian tính toán của thuật toán dựa vào phân tích các câu lệnh để tính tổng số phép tính cơ bản của chương trình.

Bước 2. Từ tổng số phép tính cơ bản của chương trình, GV hướng dẫn HS xác định độ phức tạp của thuật toán.

HOẠT ĐỘNG LUYỆN TẬP

- GV tổ chức cho HS làm Bài 1, 2 phần Luyện tập trang 117 SGK

HOẠT ĐỘNG VẬN DỤNG

- GV yêu cầu HS hoàn thành bài tập phần Vận dụng trang 117 SGK.