Giải bài 24: Đánh giá độ phức tạp thời gian thuật toán | Tin học 11 Kết nối tri thức

Tin học 11 Kết nối tri thức bài 24 Khởi động
Câu hỏi. 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? Bài làm
Chương trình 1 chạy nhanh hơn
1. Đánh giá thời gian thực hiện chương trình
Hoạt động 1: Tìm hiểu cách đánh giá thời gian thực hiện chương trì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. Bài làm
Chương trình 1: Thời gian thực hiện chương trình là T1 = T1(n) = 2 + n + 1 = n + 3 (đơn vị thời gian)
Chương trình 2: Thời gian thực hiện chương trình là T2 = T1(n) = 2 + n2 + 1 = n2 + 3 (đơn vị thời gian)
Câu hỏi 1. 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? Bài làm
a) T1 = 1 + n//3 = 1 + 1000000//3 đơn vị thời gian
b) T2 = 1 + 1 + (n//3) = 2 + 1000000//3 đơn vị thời gian
Câu hỏi 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? Bài làm
Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực" là sai vì
trong một chương trình có thể có nhiều phép toán tích cực, phụ thuộc vào mục đích
và logic của chương trình. Một phép toán được xem là tích cực khi nó đóng góp vào
sự hoàn thành tác vụ của chương trình và tối ưu hóa hiệu suất. Các phép toán tích
cực có thể bao gồm tính toán số học, truy xuất dữ liệu, ghi ra tập tin, hiển thị thông
báo cho người dùng và nhiều hơn nữa.
2. Phân tích độ phức tạp thời gian của thuật toán
Hoạt động 2: Tìm hiểu khái niệm độ phức tạp thời gian thuật toán
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. Bài làm
Thuật toán là một chuỗi các bước được thiết kế để giải quyết một vấn đề cụ thể. Một
trong những yếu tố quan trọng để đánh giá hiệu suất của một thuật toán là độ phức
tạp thời gian, tức là thời gian mà thuật toán mất để thực thi dựa trên kích thước đầu
vào của vấn đề. Phân loại thuật toán dựa trên độ phức tạp thời gian là một phương
pháp được sử dụng phổ biến để đánh giá và so sánh hiệu suất của các thuật toán
khác nhau. Dưới đây là một số phân loại chính dựa trên độ phức tạp thời gian của thuật toán:
- O(1) (độ phức tạp thời gian hằng số): Đây là loại thuật toán có thời gian thực thi
không thay đổi theo kích thước đầu vào. Thời gian thực thi của thuật toán này là cố
định, vì vậy độ phức tạp thời gian là hằng số. Ví dụ: Truy cập vào phần tử trong
mảng có kích thước cố định.
- O(log n) (độ phức tạp thời gian logarithmic): Đây là loại thuật toán có thời gian
thực thi tăng theo logarit của kích thước đầu vào. Thuật toán này thường được sử
dụng trong các bài toán tìm kiếm nhị phân, các thuật toán chia để trị, hoặc các thuật
toán sắp xếp hiệu quả như QuickSort hoặc MergeSort.
- O(n) (độ phức tạp thời gian tuyến tính): Đây là loại thuật toán có thời gian thực thi
tăng tỷ lệ trực tiếp với kích thước đầu vào. Ví dụ: Duyệt qua từng phần tử trong mảng một lần.
- O(n2) (độ phức tạp thời gian bậc hai): Đây là loại thuật toán có thời gian thực thi
tăng theo bình phương của kích thước đầu vào. Ví dụ: Thuật toán sắp xếp Bubble
Sort, các thuật toán tìm kiếm không hiệu quả như Linear Search trong một mảng lồng nhau.
- O(nk) (độ phức tạp thời gian bậc k): Đây là loại thuật toán có thời gian thực thi
tăng theo lũy thừa của kích thước đầu
Câu hỏi. Tính độ phức tạp của các hàm thời gian sau: a) Tính = 2n(n - 2) + 4. b) Tính = n3 + 5n - 3. Bài làm
a) T(n) = 2n(n - 2) + 4 = 2n2 - 4n + 4 = O(n2)
b) T(n) = n3 + 5n – 3 = O(n3)
3. Một số quy tắc thực hành tính độ phức tạp của thuật toán
Hoạt động 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. Bài làm
QT1. Quy tắc cộng: O(f(n)+g(n))=O(max(f(n),g(n))) QT2. Quy tắc nhân:
- Với hằng sô: O(C.f(n))=O(f(n))
- Với hàm số: O(f(n).g(n))=O(f(n)).O(g(n))
Câu hỏi. Á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ính = n3 + nlogn + 2n + 1. b) Tính = 3n4 + 2n2logn + 10. Bài làm a) O(n3) + 1. b) 3O(n4) + 10. Luyện tập
Câu hỏi 1: Xác định độ phức tạp thời gian cho chương trình sau: n = 1000 s = 0 for i in range (n); S = S + i(i+1) Print (S) Bài làm
Chương trình trên tính tổng các giá trị i*(i+1) trong khoảng từ 0 đến n-1 và lưu kết
quả vào biến s. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem
xét số lần lặp của vòng for và các phép toán trong vòng lặp.
Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1.000. Vậy số lần lặp là n, hay 1.000 lần.
Các phép toán trong vòng lặp:
Phép gán s = s + i*(i+1): Đây là phép gán giá trị vào biến s, có độ phức tạp là O(1).
Phép toán i*(i+1): Đây là phép nhân và cộng, có độ phức tạp là O(1).
Vậy tổng độ phức tạp thời gian của chương trình là O(n), hay O(1.000)
Câu hỏi 2. Xác định độ phức tạp thời gian tính toán cho chương trình sau: n = 1000 Sum = 0 i = 1 While i i = i*2 Sum = Sum + 1 Print (Sum) Bài làm
Chương trình trên tính số lần lặp cần thiết để i lớn hơn n bằng cách nhân i với 2
trong mỗi lần lặp, sau đó tăng biến sum lên 1. Để xác định độ phức tạp thời gian của
chương trình này, ta cần xem xét số lần lặp của vòng while và các phép toán trong vòng lặp.
Vòng while: Vòng lặp này chạy cho đến khi i >= n, và giá trị ban đầu của i là 1.
Trong mỗi lần lặp, i được nhân với 2, vậy số lần lặp là log2(n) (vì sau mỗi lần nhân
i với 2, giá trị của i sẽ gấp đôi). Ví dụ, nếu n = 1000 thì số lần lặp là log2(1000) ≈ 10.
Các phép toán trong vòng lặp:
Phép gán i = i * 2: Đây là phép nhân, có độ phức tạp là O(1).
Phép gán sum = sum + 1: Đây là phép gán giá trị vào biến sum, có độ phức tạp là O(1).
Vậy tổng độ phức tạp thời gian của chương trình là O(log n), hay O(log2(1000)) ≈ O(10) Vận dụng
Câu hỏi 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 Bài làm
Số lần so sánh giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần so sánh giữa
các phần tử là cố định, không phụ thuộc vào dữ liệu đầu vào. Cụ thể, số lần so sánh
trong thuật toán sắp xếp chọn là n(n-1)/2, với n là số phần tử trong mảng hoặc danh sách.
Số lần hoán đổi giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần hoán đổi
giữa các phần tử có thể đạt đến tối đa n-1 lần, với n là số phần tử trong mảng hoặc danh sách.
Vậy độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n^2), hay n(n-1)/2 lần
so sánh và tối đa n-1 lần hoán đổi giữa các phần tử.
Câu hỏi 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 nay. Bài làm *Chương trình 1:
from collections import Counter import time n = 1000 c = 0
# Ghi lại thời điểm bắt đầu start_time = time.time() for k in range(n): c = c + 1
# Ghi lại thời điểm kết thúc end_time = time.time()
# Tính thời gian hoàn thành
elapsed_time = end_time - start_time
# Sử dụng hàm Counter để đếm số lần lặp counter = Counter(range(n)) # In số lần lặp
print("Số lần lặp: {}".format(counter)) # In thời gian thực thi
print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time)) *Chương trình 2: import time n = 1000 c = 0
# Ghi lại thời điểm bắt đầu
start_time = time.perf_counter() for k in range(n): for j in range(n): c = c + 1
# Ghi lại thời điểm kết thúc end_time = time.perf_counter()
# Tính thời gian hoàn thành
elapsed_time = end_time - start_time # In số lần lặp
print("Số lần lặp: {}".format(c)) # In thời gian thực thi
print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))
→Sự khác biệt độ phức tạp thời gian của 2 chương trình trên:
Độ phức tạp thời gian của chương trình 1 là O(1), còn độ phức tạp thời gian của chương trình 2 là O(n2).
Document Outline

• Khởi động
• 1. Đánh giá thời gian thực hiện chương trình
• 2. Phân tích độ phức tạp thời gian của thuật toán
• 3. Một số quy tắc thực hành tính độ phức tạp của thuật toán
• Luyện tập
• Vận dụng