CHÀO MỪNG CẢ LỚP �ĐẾN VỚI BÀI HỌC HÔM NAY!
KHỞI ĐỘNG
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 n2 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à n2 + 2n, chúng ta nói độ phức tạp thời gian của phép nhân này có bậc n2.
Năm 1960, trong một tiết dạy về công nghệ thông tin, nhà toán học Nga, Viện sĩ Kolmogorov đã hỏi các sinh viên của mình là có ai tìm được cách tính phép nhân trên với thời gian tốt hơn bậc n2 được không? Đúng một tuần sau, một sinh viên tên là Karatsuba đã đưa cho Viện sĩ Kolmogorov một lời giải tốt hơn về phép tính nhân trên chỉ với độ phức tạp thời gian bậc n1,58496.
Hình minh họa
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 Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao?
Chương trình 1:
Chương trình 2:
1 n = 100
1 n = 100
Hình 24.2
Chương trình 1:
Chương trình 2:
1 n = 100
1 n = 100
Hình 24.2
Chương trình 1 chạy nhanh hơn vì chương trình 1 có 1 vòng lặp, chương trình 2 có 2 vòng lặp.
BÀI 24: ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
NỘI DUNG BÀI HỌC
01
Đánh giá thời gian thực hiện chương trình
02
Phân tích độ phức tạp thời gian thuật toán
03
Một số quy tắc thực hành tính độ phức tạp thời gian thuật toán
ĐÁNH GIÁ THỜI GIAN THỰC HIỆN CHƯƠNG TRÌNH
01
Thảo luận nhóm đôi
Hoạt động 1:
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ình 24.2
1 n = 100
Chương trình 1:
1 n = 100
Chương trình 2:
GHI 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:
Áp dụng các nguyên tắc tính khung thời gian trên chúng ta có thể tính được gần chính xác thời gian thực hiện chương trình mà không cần cài đặt và chạy chương trình trên máy tính.
Chú ý
Trong một chương trình, phép toán được thực hiện nhiều nhất và đóng vai trò chính khi thực hiện tính thời gian, được gọi là phép toán tích cực.
Ví dụ:
1 n = 100
Chương trình 1:
phép toán tích cực
1 n = 100
Chương trình 2:
phép toán tích cực
Câu hỏi củng cố kiến thức
Câu 1 (SGK-tr.113). 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?
T(n) =
4n
3
T(n) =
n
3
+ 1
Câu hỏi củng cố kiến thức
Câu 2 (SGK-tr.113). 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?
Khẳng định sai
PHÂN TÍCH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
02
Thảo luận nhóm đôi
Hoạt động 2:
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.
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 n0 ≥ 1 sao cho với mọi n ≥ n0 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ư:
Xét ví dụ:
Chương trình 1 ở Hình 24.2 có hàm thời gian T1(n) = n + 3.
Chọn c = 2, n0 = 3. Khi đó với n ≥ n0 ta có:
T1(n) = n + 3 ≤ n + n = c.n.
Do đó T1(n) = O(n). Chúng ta nói chương trình 1 có độ phức tạp thời gian O(n) - tuyến tính.
1 n = 100
Chương trình 1:
Xét ví dụ:
1 n = 100
Chương trình 2:
Chú ý
Câu hỏi củng cố kiến thức SGK - tr.114
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) = n3 + 5n – 3.
T(n) = O(n2)
T(n) = O(n3)
MỘT SỐ QUY TẮC THỰC HÀNH TÍNH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
03
Thảo luận nhóm đôi
Hoạt động 3:
Đọ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.
Quy tắc 1:
Quy tắc cộng: O(f(n) + g(n)) = O(max(f(n)))
Quy tắc này được á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.
Ví dụ: T(n) = n2 + 2n = O(max(n2, 2n)) = O(n2).
Quy tắc 2:
Quy tắc nhân:
Quy tắc này áp dụng tính độ phức tạp cho chương trình có hai vòng lặp lồng nhau.
Phép nhân với hàm số:
O(f(n).g(n)) = O(f(n).O(gn))).
Ví dụ: T(n) = 10n2 = O(n2) (Quy tắc nhân với hằng số)
T(n) = 3n2 + nlogn = O(max(3n2, nlogn)) (Quy tắc cộng) = O(3n2) = O(n2) (Quy tắc nhân với hằng số).
Vì sao khi nói đến bậc thời gian logarit thì hay chỉ viết O(logn) mà không viết cụ thể các hàm có cơ số, ví dụ log2n, log6n hay log10n?
Vì tất cả các hàm logarit đó đều cùng bậc. Điều này suy từ công thức:
logan = logab.logbn
logab là hằng số nên theo quy tắc nhân ta có logan có cùng bậc với logbn.
Á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) = n3 + nlogn + 2n + 1.
b) T(n) = 3n4 + 2n2logn + 10.
Câu hỏi củng cố kiến thức SGK - tr.114
= O(n3) (Quy tắc cộng).
= O(3n4) (Quy tắc cộng) = O(n4) (Quy tắc nhân với hằng số).
BÀI TẬP TRẮC NGHIỆM
Câu 1: Giả sử một chương trình P mô tả một thuật toán nào đó. Người ta đo được các thông tin thời gian sau:
Khi đó thời gian chạy chương trình T(n) dùng để tính độ phức tạp thời gian của thuật toán là phương án nào trong các phương án sau?
A. T1 + T2.
B. T2
C. T2 + T3.
D. T1 + T2 + T3
Câu 2: Cho chương trình sau:
1 <input n - số tự nhiên dương>
2 S = 0
3 for i in range(1, n + 1):
4 S = S + i*i
5 print(S)
Kết quả đánh giá thời gian chạy chương trình T(n) là:
A. n + 2
B. 2n
C. n2
D. log2n.
Câu 3: Độ phức tạp của hàm n + 2n.log2(n) + 10 theo kí hiệu O-lớn là:
A. n
B. 2n
C. nlog2n
D. nlogn
Câu 4: Độ phức tạp của hàm 2n2 + 3n3log5(n) + n3/2 theo kí hiệu O-lớn là:
A. 2n2
B. 2n2 + n3.logn.
C. n3.logn.
D. n3/2.
Câu 5: Độ phức tạp của hàm 2n + 3n + 5n theo kí hiệu O-lớn là
A. 2n.
B. 3n.
C. 4n.
D. 5n.
LUYỆN TẬP
Bài 1 (SGK - tr.114). Xác định độ phức tạp thời gian tính toán cho chương trình sau:
1 n = 1000
2 S = 0
3 for i in range (n):
4 S = S + i(i+1)
5 print(S)
T(n) = 2n + 2 = O(n)
Bài 2 (SGK - tr.114). Xác định độ phức tạp thời gian tính toán cho chương trình sau:
1 n = 1000
2 Sum = 0
3 i = 1
4 while i < n:
5 i = i*2
6 Sum = Sum + i
7 print(Sum)
T(n) = 2log2n + 2 = O(logn)
VẬN DỤNG
Bài 1 (SGK - tr.114). 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.
Các thuật toán sắp xếp đã học đều có độ phức tạp thời gian O(n2).
Bài 2 (SGK - tr.114). Em hãy thiết lập chương trình và tính thời gian 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.
Hình 24.2
1 n = 100
Chương trình 1:
1 n = 100
Chương trình 2:
Chương trình có thể thực hiện như sau:
HƯỚNG DẪN VỀ NHÀ
1
2
3
Ghi nhớ kiến thức đã học trong bài
Hoàn thành bài tập trong SBT
Chuẩn bị bài mới - Bài 25
CẢM ƠN SỰ CHÚ Ý
LẮNG NGHE CỦA CÁC EM!