题目
给定以下程序int MaxSum(int n, int a[])int sum=0, b=0;for (int i=1; i0) b+=a[i]; else b=a[i]; if (b>sum) sum=b;}return sum;其时间复杂度是O( )。A. nB. n^2C. log nD. nlog n
给定以下程序
int MaxSum(int n, int a[])
int sum=0, b=0;
for (int i=1; i<=n; i++) {
if (b>0) b+=a[i];
else b=a[i];
if (b>sum) sum=b;
}
return sum;
其时间复杂度是O( )。
A. n
B. $n^2$
C. $\log n$
D. n$\log n$
题目解答
答案
A. n
解析
本题考查算法时间复杂度的计算。解题思路是分析程序中基本操作的执行次数与问题规模之间的关系。
下面来详细分析该程序:
- 程序中定义了两个变量
sum和b并初始化为 0,这是常数时间操作,不影响时间复杂度。 - 进入
for循环,循环条件为i从 1 到n,循环体中包含两个if语句。- 第一个
if语句if (b>0) b+=a[i]; else b=a[i];,无论b的值如何,都会执行一次赋值或加法操作。 - 第二个
if语句if (b>sum) sum=b;,同样会执行一次比较操作。
- 第一个
- 整个
for循环会执行n次,每次循环内的操作都是常数时间操作,即每次循环的时间复杂度为 $O(1)$。 - 根据时间复杂度的计算规则,循环执行
n次,每次操作时间复杂度为 $O(1)$,那么总的时间复杂度为 $O(n\times1)=O(n)$。