计算时间复杂度（分析过程）

Question

设n是偶数，运行下面的程序段后计算语句m=m+1的次数，并给出该程序段的时间复杂度。
m=0;
for(i=1; i<=n; i++)
for(j=2*i; j<=n; j++)
m=m+1;

Answer 1

 次数=n*(n/2)/2=0.25*n^2
所以O(n)=n^2
这是等差数列求和公式，对于内循环，第一次循环n次，第二次n-2，第三次n-4...直到0，也就是2*i>n就不循环了。对于整个程序，就是所有内循环次数求和。