Giáo án điện tử 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

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

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 n² đượ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 n^1,58496.

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

Thảo luận nhóm đôi

                            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.

Chương trình 1:

1  n = 100

• C = 0
• for k in range (n):
• C = C + 1
• print(C)

Chương trình 2:

1  n = 100

• C = 0
• for i in range (n):
• for j in range(n):
• C = C + 1
• print(C)

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:

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

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

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?

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

02 PHÂN TÍCH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

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

Xét ví dụ:

Chương trình 1 ở Hình 24.2 có hàm thời gian T₁(n) = n + 3.

Chọn c = 2, n₀ = 3. Khi đó với n ≥ n₀  ta có:

T₁(n) = n + 3 ≤ n + n = c.n.

Do đó T₁(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.

Chương trình 1:

1  n = 100

• C = 0
• for k in range (n):
• C = C + 1
• print(C)

Chương trình 2 ở Hình 24.2 có hàm thời gian T₂(n) = n² + 3.

Chọn c = 2, n₀ = 2. Khi đó với n ≥ n₀, ta có:

T₂(n) = n² + 3 < n² +  = 2n² = c.n².

Vậy suy ra T₂(n) = O(n²). Ta nói chương trình 2 ở trên có độ phức tạp thời gian O(n²) - bình phương.

Chương trình 2:

1  n = 100

• C = 0
• for i in range (n):
• for j in range(n):
• C = C + 1
• print(C)

Chú ý