算法复杂度T(n)推算

int i;for(i=0;i<n;i++){/*...*/};这里int 执行一次，for循环里的语句执行n次，所以T(n)=n+1;但是当n变大时，这个常数就显得无足轻重了，所以它的算法复杂度为O(n)。
同样的，对于下面的代码：
int i,j;for(i=0;i<n;i++)    for(j=0;j<n;j++){/*...*/};这里int 执行一次，嵌套的for执行了n*n次，所以T(n)=n2+1;同理，它的复杂度为O(n2)。
那么，下面的代码算法复杂度为多少呢？
int i,j;  for(i=0;i<n;i++)    for(j=i;j<n;j++){/*...*/};这段代码，int 执行一次，下面的for执行了n+(n-1)+(n-2)+...+1次，所以Ｔ(n)=1+(1+n)*n/2=n2/2+n/2+1。当n增大时，1和n/2都显得无足轻重了，只剩下n2/2,但是之前说过大O只考虑阶数，所以复杂度应该为O(n2)
再来看看下面的代码：
int i=1;while(i<n)    i*=2;每次执行i都乘以2，设执行次数为x，那么2x≥n，我们只取等于的情况，得到x=log2n。所以这个循环的复杂度为O(logn)，底数大小其实在n很大的时候是无足轻重的，所以不做考虑。