下面程序的时间复杂度是？

Question

S=0
for(i=0;i<n;i++)
for(j=0;j<n;j++)
s+=b[i][j];
sum=s;
希望能有解释，不单单只是一个简单答案。

Answer 1

时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数
该程序
S=0; -------这里是常数O(1),
for(i=0;i<n;i++)
for(j=0;j<n;j++)
s+=b[i][j]; ----这里是n的平方，用平方阶表示O(n^2)
sum = s;-------这里是常数O(1)

所以上述时间复杂度是T(n) = 两个常数O(1) + n的平方，两个常数相对n的平方来说是低阶项去掉，即常数阶可以去掉忽略不计。
最终时间复杂度是T(n) = O(n^2)