Luyện tậpCâu hỏi 1. Xác định độ phức tạp thời gian cho chương trình sau:n = 1000s = 0for i in...

Để giải câu hỏi trên, ta cần xác định độ phức tạp thời gian của chương trình đã cho.

- Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1000. Vậy số lần lặp là n, tức là 1000 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ũng có độ phức tạp là O(1).

Tổng độ phức tạp thời gian của chương trình là O(n), hay O(1000). Độ phức tạp của chương trình này tương đương với độ phức tạp thời gian O(n) với n = 1000. Đồng thời, độ phức tạp không phụ thuộc vào giá trị cụ thể của n mà chỉ phụ thuộc vào số lần lặp của vòng for.