BÀI 24. ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
Trang bìa
Trang bìa
Ảnh
TIN HỌC 11
BÀI 24. ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
Ảnh
Mục tiêu bài học
Mục tiêu
Ảnh
Mục tiêu:
Biết cách phân tích phân độ phức tạp thời gian thuật toán. Nhận và 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.
Khởi động
Khởi động
Ảnh
Ảnh
- Khởi động:
Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong H24.2. Chương trình nào chạy nhanh hơn? Vì sao?
Hình thành kiến thức
1. Đánh giá thời gian thực hiện chương trình
Ảnh
1. Đánh giá thời gian thực hiện chương trình
Không cần cài đặt và chạy chương trình, tính tổng thời gian các phép tính đơn và các lệnh đơn của chương trình. Dùng để so sánh và ước lượng thời gian chạy chương trình. Coi tất cả các lệnh đơn và các phép tính đơn có thời gian chạy như nhau, gọi là một đơn vị thời gian. Đơn giản hoá cách phân tích thời gian tính toán và bảo đảm độ chính xác của tính toán.
- HĐ1: Tìm hiểu cách đánh giá thời gian thực hiện CT
Ảnh
Quan sát và thực hiện đánh giá thời gian chạy của các chương trình 1 và 2 trong Hình 24.2. Từ đó biết và hiểu được cách đánh giá thời gian thực hiện chương trình.
- HĐ1: Tìm hiểu cách đánh giá thời gian thực hiện CT
Ảnh
- Gợi ý
Ảnh
- Gợi ý:
+ Chương trình 1: Gọi latex(T_1) là thời gian chạy của chương trình này.
* Lệnh tại dòng 1 và 2 cần 1 đơn vị thời gian. * Vòng lặp tại dòng 3 có n bước lặp, mỗi bước của vòng lặp sẽ thực hiện lệnh tại dòng 4, lệnh này cần 1 đơn vị thời gian. Tổng thời gian của vòng lặp 3 là n thời gian. * Lệnh cuối tại dòng 5 cần 1 đơn vị thời gian. => Thời gian thực hiện toàn bộ chương trình 1 cần: latex(T_1 = T_1(n) = n + 3) đơn vị thời gian.
+ tiếp (- Gợi ý)
Ảnh
+ Chương trình 2: Gọi latex(T_2) là thời gian chạy của chương trình này.
* Lệnh tại dòng 1 và 2 cần 1 đơn vị thời gian. * Hai vòng lặp lồng nhau tại dòng 3, 4 có n2 bước lặp. Mỗi bước lặp sẽ thực hiện lệnh tại dòng 5, lệnh này cần 1 đơn vị thời gian. * Tổng thời gian của vòng lặp 3, 4 là latex(n^2) đơn vị thời gian. * Lệnh cuối tại dòng 6 cần 1 đơn vị thời gian. => Tổng hợp toàn bộ chương trình 2 ta có: latex(T_2 = T_2(n) = n2 + 3) đơn vị thời gian.
- Ghi nhớ
- Ghi nhớ:
Ảnh
Cách đánh giá thời gian chạy chương trình được dựa trên một bộ khung các nguyên tắc dùng làm căn cứ để tính toán. Các nguyên tắc khung như sau: 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ẽ tính 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.
+ tiếp
- Ghi nhớ:
Ảnh
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.
- Lưu ý
Ảnh
Phép toán được thực hiện nhiều nhất và đóng vai trò chính khi tính thời gian, được gọi là phép toán tích cực. Ví dụ trong chương trình 1, phép cộng C = C + 1 tại dòng 4 là phép toán tích cực. Trong chương trình 2, phép cộng C = C + 1 tại dòng 6 là phép toán tích cực.
- Lưu ý:
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
1. Các lệnh và đoạn chương tình sau cần chạy trong bao nhiêu đơn vị thời gian?
Ảnh
2. Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực" là đúng hay sai?
2. Phân tích độ phức tạp thời gian thuật toán
2. Phân tích độ phức tạp thời gian thuật toán
- HĐ2: Tìm hiểu khái niệm độ phức tạp thời gian thuật toán
Ảnh
Cùng trao đổi và tìm hiểu cách phân loại thuật toán dựa trên độ phức tạp thời gian thuật toán.
- Tìm hiểu
- Tìm hiểu:
Ảnh
Độ phức tạp thời gian của thuật toán là khối lượng thời gian cần thiết để chạy chương trình thể hiện thuật toán. Phân loại thuật toán dựa trên ước lượng độ phức tạp thời gian. Độ phức tạp thời gian có thể coi là một hàm số T(n) với n là số tự nhiên đại diện cho dữ liệu đầu vào. Giá trị của T(n) được xác định trên cơ sở số lượng phép toán/câu lệnh cần thực hiện trong chương trình/thuật toán. Kí hiệu O-lớn được sử dụng để so sánh và phân tích bậc của hàm thời gian T(n) khi n tiến tới vô cùng.
- Định nghĩa O lớn
Ảnh
- Định nghĩa O lớn:
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 latex(n_0 >= 1) sao cho với mọi latex(n >= n_0), ta có latex(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)).
- Ví dụ
Ảnh
- Ví dụ:
* Chương trình 1 ở H24.2 có hàm thời gian latex(T_1(n) = n + 3). Chọn c = 2, latex(n_0 = 3). Khi latex(n >= n_0), ta có: latex(T_1(n) = n + 3 <= n + n = c.n). Do đó, latex(T_1(n) = O(n)). Chương trình 1 có độ phức tạp thời gian O(n) - tuyến tính. * Chương trình 2 ở H24.2 có hàm thời gian latex(T_2(n) = n^2 + 3). Chọn c = 2, latex(n_0 = 2). Khi latex(n >= n_0), ta có: latex(T_2(n) = n^2 + 3 < n^2 + n_0^2 <= n^2 + n^2 = 2n^2 = c.n^2). Suy ra latex(T_2(n) = O(n^2)). Chương trình 2 có độ phức tạp thời gian latex(O(n^2)) - bình phương.
- Ghi nhớ
- Ghi nhớ:
Ảnh
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. 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, latex(O(n^2)) - bình phương, latex(O(n^k)) - đa thức, latex(O(a^n)) - luỹ thừa, O(n!) - giai thừa.
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
Ảnh
Tính độ phức tạp của các hàm thời gian sau: a) T(n) = 2n(n - 2) + 4. b) T(n) = latex(n^3 + 5n - 3).
3. Một số quy tắc thực hành tính độ phức tạp thời gian thuật toán
Ảnh
3. Một số quy tắc thực hành tính độ phức tạp thời gian thuật toán
- HĐ3: Tìm hiểu một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán
Đọc, quan sát, thảo luận để biết một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán.
- Tìm hiểu
- Tìm hiểu:
Quy tắc tính đơn giản độ phức tạp thời gian thuật toán:
QT1. Quy tắc cộng: O(f(n) + g(n)) = O(max(f(n), g(n))). Áp dụng khi tính độ phức tạp thời gian cho hai chương trình được thực hiện nối tiếp nhau. QT2. Quy tắc nhân: Phép nhân với hằng số: O(C.f(n)) = O(f(n)), với C là hằng số bất kì. Phép nhân với hàm số: O(f(n).g(n)) = O(f(n).O(g(n))). Áp dụng tính độ phức tạp thời gian cho chương trình có hai vòng lặp lồng nhau.
Ảnh
- Ví dụ
Ảnh
- Ví dụ:
T(n) = latex(10n^2 = O(n^2)) (Quy tắc nhân với hằng số). T(n) = latex(3n^2 + nlogn = O(max(3n^2, nlogn))) (Quy tắc cộng) = latex(O(3n^2) = O(n^2)) (Quy tắc nhân với hằng số).
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
Ảnh
Áp dụng các quy tác trên để tính độ phức tạp của các hàm thời gian sau: a) T(n) = latex(n^3 + nlogn + 2n + 1). b) T(n) = latex(3n^4 + 2n^2logn + 10).
Luyện tập
- Câu 1 (- Luyện tập)
Ảnh
- Luyện tập
Hình vẽ
Câu 1: Xác định độ phức tạp thời gian cho chương trình sau:
Ảnh
- Câu 2 (- Luyện tập )
Ảnh
Hình vẽ
Câu 2: Xác định độ phức tạp thời gian tính toán cho chương trình sau:
Ảnh
Vận dụng
- Vận dụng
Ảnh
- Vận dụng:
1. Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn đã được học trong bài 21. 2. Em hãy thiết lập chương trình và tính thời gian chạy thực tế trên máy tính của các chương trình 1 và 2 ở Hình 24.2 với các giá trị n khác nhau từ đó thấy được ý nghĩa sự khác biệt độ phức tạp thời gian của hai chương trình này.
Dặn dò
Dặn dò
Ảnh
Dặn dò:
Ôn lại kiến thức vừa học. Làm bài tập trong SBT. Chuẩn bị bài sau: "Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán".
Cảm ơn
Ảnh