Câu hỏi:
20/04/2023 1,053Xá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)
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
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 HOT CÙNG CHỦ ĐỀ
Câu 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?
Câu 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?
Câu 3:
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)
Câu 4:
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âu 5:
Á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 6:
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.
về câu hỏi!