一个低效的前缀求和,(c++)
void inef(T a[], T b[],int n)
{
for (int j=0;j<n;j++)
b[j]=Sum(a,j+1);
}
其中这个程序的分析中 第三步
b[j]=Sum(a,j+1);
分析时间复杂性的时候算执行步数
其中“s/e”值为2j+6 频率为n
为什么最后总步数为n(n+5)?
參考答案:分析第一个for循环语句执行一次的过程:
进入第一个for循环,判断若i小于n,执行第二个for循环,判断若j小于i,执行S语句,S语句执行完毕,返回第二个for循环,j的值加1,继续判断j是否小于或等于i,若j满足小于或等于i的条件,继续执行S语句,直到j大于i,退出第二个for循环,返回第一个for循环,i的值加1,此时第一个for循环的一次执行过程结束。
接着,判断i的值是否满足i小于或者等于n的条件,若满足,进入第一个for循环下一次的循环,若不满足,退出第一个for循环的循环结束。
从以上的执行过程可以知道,执行S的次数为1,2,3……n,所以次数和为n(n+1)/2