数据结构初级问题 时间复杂性

来源：百度知道 编辑：UC知道 时间：2024/06/30 21:41:02
一个低效的前缀求和，（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