S=0
for i in range(1,100,2):
S=S+i
print(S)
a) Cho biết giá trị của S là bao nhiêu khi thực hiện chương trình?
b) Tính thời gian thực hiện của thuật toán T(n)
c) Ước lượng độ phức tạp về thời gian O(n)
Quảng cáo
1 câu trả lời 364
a) Đoạn chương trình trên tính tổng của các số lẻ từ 1 đến 99. Để tính giá trị của \(S\), chúng ta thực hiện vòng lặp và cộng thêm giá trị của mỗi số lẻ vào biến \(S\).
\[
S = 1 + 3 + 5 + \ldots + 99
\]
Đây là cách tính tổng của một dãy số hình học. Đối với dãy số hình học, công thức tổng quát là \(S = \frac{n(a_1 + a_n)}{2}\), trong đó \(n\) là số lượng số trong dãy, \(a_1\) là số đầu tiên và \(a_n\) là số cuối cùng trong dãy.
Ở đây, \(n = \frac{99 - 1}{2} + 1 = 50\) (vì có 50 số lẻ từ 1 đến 99). Ta có \(a_1 = 1\) và \(a_n = 99\).
Thay vào công thức, ta có:
\[
S = \frac{50 \times (1 + 99)}{2} = \frac{50 \times 100}{2} = 2500
\]
Vậy giá trị của \(S\) là 2500.
b) Đoạn chương trình có một vòng lặp \(for\) chạy từ 1 đến 99, mỗi lần lặp lại thực hiện một phép cộng. Vậy thời gian thực hiện của thuật toán \(T(n)\) là \(O(n)\), trong đó \(n = 50\) là số lần lặp lại.
c) Độ phức tạp về thời gian của thuật toán là \(O(n)\), bởi vì thời gian thực hiện tăng theo tỉ lệ tuyến tính với đầu vào \(n\) (trong trường hợp này là số lần lặp lại của vòng lặp).
Quảng cáo
Bạn muốn hỏi bài tập?
