Question

有一道数据额结构的题目不是很明白，for（i=0；i<n；i++） ,for（j=0；j<n；j++）, s++。

答案是该程序的语句执次数f（n）=n+1+n(n+1)+n*n=2n*n+2n+1，时间复杂度为T（n）=O（f（n））=O（n*n）（注n*n表示n乘以n）。请问语句执行次数和时间复杂度是怎么算出来的？

Answer 1

首先这个程序最占用时间的3条语句是：i++，j++，s++。(本来i=0；i<n；j=0；j<n；这4条都是语句，但是估计考虑到这四条执行的时间很快，所以忽略不计了)。

接下来说上面3条语句的执行时间，你的程序等价于下面这种格式：

for（i=0；i<n；i++)
{
    for（j=0；j<n；j++）
    { 
        s++;
    }
}

这个一个双重循环，处于循环最里面的s++执行了n*n次，这个应该不难理解吧。

j++执行了n*(n+1)次：因为外层i执行了n次，j执行了n+1次。

i++执行了n+1次。

T(n)=O(f(n)) = O(2n*n+2*n+1)。但是我们说的是复杂度，复杂度的表示一般都只要把表示数据增长的性质表达出来就行了，而且是影响数据增长最主要的性质。何为数据增长的性质，比如说n，那就是线性增长；n*n，那就是平方增长，n*n*n，那就是3次方增长；log（n），那就是对数增长。以上综合，影响2n*n+2*n+1最主要的增长性质是n*n。所以复杂度就是O(n*n)。

Answer 2

f(n)也就是语句执行次数是指所有语句执行的总次数，也就是for（i=0；i<n；i++）执行了n+1次
for（j=0；j<n；j++）执行了n(n+1)次，s++执行了n*n次。
O(n)出自大O算法，就是时间复杂度，也就是在最坏情况下语句执行次数，实际上就是f(n)的最高次幂，也就是2n*n+2n+1中的n*n，前面的常数无所谓