不考虑运算常量,
A: for (i=2;i<=n;i++)
B: for(j=2;j<=i-1;++j)
{
C: ++x;a[i j]=x;
}
A 执行1次,B 执行n-1次,问 C 执行几次?
因为 B 的时间复杂度是依赖于参数i的,所以 C 也同样依赖于参数i,
列出关系:
O(A) = O(B2)+O(B3)+...+O(Bn)
O(Bi) = O(Ci,2)+O(Ci,3)+...+O(Ci,i-1)
设 O(Ci,j) = 1
求得
O(Bi) = ((i-1) - 2) + 1 = i-2
O(A) = 0 + 1 + ... + (n-2) = (1+n-2)*(n-2)/2 = n2 - 3/2n + 1
约去低阶分量,O(A)=n2.
温馨提示:内容为网友见解,仅供参考