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

王朝知道·作者佚名  2009-06-26
窄屏简体版  字體: |||超大  
 
分類: 電腦/網絡 >> 程序設計 >> 其他編程語言
 
問題描述:

一个低效的前缀求和,(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

小贴士:① 若网友所发内容与教科书相悖,请以教科书为准;② 若网友所发内容与科学常识、官方权威机构相悖,请以后者为准;③ 若网友所发内容不正确或者违背公序良俗,右下举报/纠错。
 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航