主题：关于时间复杂度的计算
66187564
[专家分：0] 发布于 2007-02-18 23:19:00
代码如下：
i=0;s=0;
while(s < n) do
{
i=i+1;s=s+i;
}
时间复杂度为什么是：O(√n) 啊？
是怎么算的啊？
回复列表 （共12个回复）
沙发
雪光风剑 [专家分：27190] 发布于 2007-02-19 02:56:00
累加的时间复杂度阿
具体计算不是太清楚，等rickone来写计算过程
但是理由是累加和为不大于n的数的累加次数收敛于sqrt(n)
板凳
argentmoon [专家分：13260] 发布于 2007-02-19 10:17:00
实质上,这题目就是累加:
1 + 2 + .. + x = n
所以 x * ( x + 1) / 2 = n
解x出来就是了
3 楼
66187564 [专家分：0] 发布于 2007-02-19 11:28:00
还是不明白，楼上X指的是什么啊？
4 楼
argentmoon [专家分：13260] 发布于 2007-02-19 23:14:00
你首先要看清楚计算过程,看清楚了就知道是一个累加过程,那么这个循环的结束条件是什么呢? 未知,我们设最后一个数为x
所以1 + 2 + ... + x < n
5 楼
雪光风剑 [专家分：27190] 发布于 2007-02-20 01:19:00
我已经明白是怎么回事了
我来说完吧
1+2+...+x根据累加公式，就=(x+1)*x/2（联想梯形面积公式）
解出来这个式子就是(x^2)/2+x/2<=n
算法的时间复杂度只取决于最高次数，所以时间复杂度为x循环的次数也就是不大于sqrt(n)
6 楼
rickone [专家分：15390] 发布于 2007-02-20 01:34:00
[quote]
i=0;s=0;
while(s < n) do
{
i=i+1;s=s+i;
}
[/quote]
现在是要找循环次数t和n的函数关系，用n表示t难，就用t表示n，循环了t次后s>=n，则至少s==n，s=1+2+...+t，至少n=1+2+...+t，解出t就行了。
7 楼
智商大于一百 [专家分：20] 发布于 2007-02-27 10:51:00
算法下界就是最坏的情况：就是说，按所有的循环都要循环一次的方式计算
x * ( x + 1) / 2 < n，X就是要运算的次数（等差数列求和，是吧？）
while(s < n) do，就是说最多要循环x次
{
i=i+1;s=s+i;
} 每次循环要执行4个任务（2次加赋值），运算4次
所以你的循环在最坏的情况下要运算：4*n 次
i=0;s=0; 赋值执行2个任务，运算2次
一共是： 4*x+2 次。所以这个是 指数阶的算法
（我不知道对不对，昨天才学的 算法效率的计算
这个问题很复杂吧？
8 楼
rickone [专家分：15390] 发布于 2007-02-27 21:52:00
[quote]算法下界就是最坏的情况：就是说，按所有的循环都要循环一次的方式计算
x * ( x + 1) / 2 < n，X就是要运算的次数（等差数列求和，是吧？）
while(s < n) do，就是说最多要循环x次
{
i=i+1;s=s+i;
} 每次循环要执行4个任务（2次加赋值），运算4次
所以你的循环在最坏的情况下要运算：4*n 次
i=0;s=0; 赋值执行2个任务，运算2次
一共是： 4*x+2 次。所以这个是 指数阶的算法
（我不知道对不对，昨天才学的 算法效率的计算
这个问题很复杂吧？
[/quote]
就这个意思。算法效率的计算不是‘一个’问题，是设计算法应该考虑的最主要方面。
9 楼
雪光风剑 [专家分：27190] 发布于 2007-03-01 08:33:00
[quote]算法下界就是最坏的情况：就是说，按所有的循环都要循环一次的方式计算
x * ( x + 1) / 2 < n，X就是要运算的次数（等差数列求和，是吧？）
while(s < n) do，就是说最多要循环x次
{
i=i+1;s=s+i;
} 每次循环要执行4个任务（2次加赋值），运算4次
所以你的循环在最坏的情况下要运算：4*n 次
i=0;s=0; 赋值执行2个任务，运算2次
一共是： 4*x+2 次。所以这个是 指数阶的算法
（我不知道对不对，昨天才学的 算法效率的计算
这个问题很复杂吧？
[/quote]
有点问题
你的时间代价计算上有偏差
你把最主要的累加时间代价一笔带过了，而那恰恰是时间代价的衡量因素（因为引起了时间代价的指数变化）而常系数和常数项对于时间代价来说没有那么大的衡量价值
10 楼
66187564 [专家分：0] 发布于 2007-03-01 22:17:00
真后悔当初数学没学好
我来回复
您所在位置：