刚学数据结构,遇到一道题,无从下手啊
分析下面语句段执行的时间复杂度.
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s++;
问题点数：20、回复次数：10Top
1 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-09-22 21:48:34 得分 0
晕~~
典型的
O(n^2)时间复杂度嘛!!!!Top
2 楼brightnox（）回复于 2005-09-22 22:09:09 得分 0
楼上的大哥哥,能帮我进一下吗?为什么啊?实在是有点不好意思问!Top
3 楼Ngufer（rocker）回复于 2005-09-22 22:26:53 得分 10
第一个for要执行n次,而第一个for每执行一次时第二个for都要执行n次,也就是全程序要执行n*n个语句,所以他的时间复杂性是O(n*n)
我一直是这样理解的,虽不是很精确,但总能说明问题Top
4 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-09-22 22:30:43 得分 0
一般就是这么算的Top
5 楼brightnox（）回复于 2005-09-22 23:13:50 得分 0
for(i=1;i<=n;i++)
for(j=i;j<=i;j++)
s++;
呢???Top
6 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-09-23 07:49:51 得分 0
for(j=i;j<=i;j++)
---------------
j<=i?????????
那内层循环只执行一次啊!
那就是O(n*1)Top
7 楼yzx1983（捕风捉影）回复于 2005-09-23 09:41:57 得分 0
楼主在楼上的楼上的回复一定是打错了……
想必应该是
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
s++;Top
8 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-09-23 09:43:31 得分 5
那执行次数是
n(n+1)/2
所以算法的复杂度还是O(n*n)Top
9 楼yzx1983（捕风捉影）回复于 2005-09-23 09:44:54 得分 5
这样的时间复杂度算式该是
1+2+3+..+n＝n(n+1)/2=n^2/2+n/2
复杂度取指数最高项并忽略其系数，所以这个复杂度仍然是O(n^2).Top
10 楼yzx1983（捕风捉影）回复于 2005-09-23 09:45:43 得分 0
哎呀，比楼上慢了一步……^_^Top
