Xác định độ phức tạp thời gian cho chương trình sau: n = 1000

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

Luyện tập 1 trang 114 Tin học 11: 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)

Lời giả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)