关于数据结构中的时间复杂度问题

august

定义是说通常把算法中所包含的简单操作次数称为算法的时间复杂度，其通常用 O（1），O（n),
O(n!)等形式表示，而其中如果运行时间与n成正比，其时间复杂度就是O(n).
下面一程序：
void fun3(int n)
{
     int i=0,s=0;
     while(s<n)
      {
          i++;
          s=s+i;
       }
}

为什么其时间复杂度是如图所示，而不是O(n)呢？

希德船长

怎么说呢。。。那while循环并不是n次，而是近似为n的平方根次。。。因为每次循环，s的值并不是只增加1。。。。。。这结论好像用数学手段能推导出来。。。。

august

那能否推出来看看呢？ [s:2]  [s:2]

Zelsazgh

因为s=1+2+3+4.....+n=n*(1+n)*2
要满足s<n
第一次 1=1          时间为1
第二次 1+2=3      时间为2
第三次 1+2=3      时间为2
第四次 1+2+3=6  时间为3
......可以看出随N增大,时间基本向sqrt(N)发展....