Video 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

Xin chào các em học sinh thân mến, chúng ta lại gặp nhau trong bài học ngày hôm nay rồi!

Thông qua video này, các em sẽ nắm được các kiến thức và kĩ năng như 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.

HOẠT ĐỘNG KHỞI ĐỘNG

Trước khi bước vào bài học ngày hôm nay, em hãy 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 n² 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à n² + 2n, chúng ta nói độ phức tạp thời gian của phép nhân này có bậc m². 

HOẠT ĐỘNG KHÁM PHÁ

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

Video trình bày nội dung:

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.

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

Video trình bày nội dung:

- 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.

………..

Nội dung video Bài 24: Đánh giá độ phức tạp thời gian thuật toán còn nhiều phần rất hấp dẫn và thú vị. Hãy cùng đăng kí để tham gia học bài và củng cố kiến thức thông qua hoạt động luyện tập và vận dụng trong video.