Slide bài giảng 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

Tóm lược nội dung

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

KHỞI ĐỘNG

- GV dẫn dắt, đặt vấn đề cho HS: Quan sát Hình 24.1, ta nhận thấy rằng việc nhân hai số có n chữ số sẽ yêu cầu n² phép nhân và 2n phép cộng. Do đó, tổng số phép tính đơn trong phép nhân này là n² + 2n, và chúng ta có thể nói rằng độ phức tạp thời gian của phép nhân này có bậc m²

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

•  Tìm hiểu về đánh giá thời gian thực hiện chương trình

•  Tìm hiểu về phân tích độ phức tạp thời gian thuật toán

• Luyện tập

• Vận dụng

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

1. Các phép toán đơn giản như phép tính số học + - */ phép lấy thương nguyên và số dư, các phép so sánh sẽ tinh là 1 đơn vị thời gian. 

2. Các phép toán lôgic cơ bản như AND, OR, NOT sẽ tính là 1 đơn vị thời gian. 

3. Các lệnh đơn như lệnh gán, lệnh in, đọc dữ liệu.... tính là 1 đơn vị thời gian.

4. Vòng lặp for hoặc while sẽ được tính thời gian bằng tổng đơn vị thời gian thực hiện của mỗi bước lặp.

5. Lệnh if với nhiều trường hợp rẽ nhánh sẽ được tính thời gian bằng đơn vì thời gian lớn nhất của các lệnh nhánh.

Hoạt động 2: Tìm hiểu về 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 n₀ ≥ 1 sao cho với mọi n ≥ n₀ 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(n²) - bình phương

O(n^k) - đa thức

O(aⁿ) - lũy thừa

O(n!) - giai thừa.

HOẠT ĐỘNG LUYỆN TẬP, THỰC HÀNH

Câu 1: Thuật toán tối ưu là?

A. Sử dụng ít thời gian, ít bộ nhớ…

B. Sử dụng ít thời gian, nhiều bộ nhớ, ít phép toán…

C. Sử dụng nhiều thời gian, nhiều bộ nhớ, ít phép toán…

D. Sử dụng ít thời gian, ít bộ nhớ, ít phép toán…

Câu 2: Các bước cần phải có khi giải bài toán trên máy tính là:

A. Xác định bài toán, lựa chọn hoặc thiết kế thuật toán, diễn tả thuật toán, hiệu chỉnh, viết tài liệu

B. Xác định bài toán, lựa chọn hoặc thiết kế thuật toán, viết chương trình, viết tài liệu

C. Xác định bài toán, lựa chọn hoặc thiết kế thuật toán, viết chương trình, hiệu chỉnh, viết tài liệu

D. Xác định bài toán, viết thuật chọn, viết chương trình, viết tài liệu

Câu 3: Các lệnh và đoạn chương trình sau cần chạy trong bao nhiêu đơn vị thời gian?

A. 3 đơn vị thời gian

B. 1 đơn vị thời gian

C. 2 đơn vị thời gian

D. 5 đơn vị thời gian

Câu 4: Tính độ phức tạp của các hàm thời gian sau:

Tính = 2n(n - 2) + 4.

A. O(n) - tuyến tính

B. O(n^{3}) - lũy thừa

C. O(n^{1}) - lũy thừa

D. O(n^{5}) - lũy thừa

Câu 5: Tính độ phức tạp của các hàm thời gian sau:

Tính = n³ + 5n - 3.

A. O(n) - tuyến tính

B. O(n³) - lũy thừa

C. O(n¹) - lũy thừa

D. O(n⁵) - lũy thừa

Đáp án gợi ý:

Câu 1: D

Câu 2: C 

Câu 3: A

Câu 4: C 

Câu 5: B

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

- GV yêu cầu HS hoạt động cặp đôi hoàn thành bài tập phần Vận dụng trang 114 SGK.