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 <n;
i = i*2
sum = sum + 1
print (sum)
Vận dụng kiến thức trong bài và kiến thức thực tế của bản thân để trả lời câu hỏi.
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)
Các bài tập cùng chuyên đề
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?
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.
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?
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?
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í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.
Đọ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.
Á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.
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)
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.
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.
