题目

关于一道数据结构计算时间复杂度的问题
例题如下:
FOR i:=1 TO n DO ----------{n+1}
FOR j:=1 TO n DO ----------{n*(n+1)}
[ c[i,j]:=0; -------------{n的2次方}
FOR k:=1 TO n DO ----------{n的2次方*(n+1)}
c[i,j]:=c[i,j]+a[i,k]*b[k,j] --------{n的3次方}
]
[解] T(n)=2*n的3次方 +3*n的2次方 +2*n+1
请问程序第一行的FOR i:=1 TO n DO 为什么是n+1而不是n呢?还有第二行为什么是n*(n+1)呢?到底哪层循环是n?哪层循环是n+1?

提问时间：2020-10-30

答案

n+1次是最后跳出循环体时的比较..不算进循环体.
然而后面变成n,因为循环n次..(不是n+1)
都个循环次都是n..
FOR i:=1 TO n DO ----------{n+1} //对下行来说,只有n次.
FOR j:=1 TO n DO ----------{n*(n+1)}