渐近复杂度

绝了，印象笔记的MARKDOWN和MarkdownPad2 的不一样的吗。

上完MOOC之后我发现我对渐近复杂度的求法充满迷茫，于是我去翻了一眼我校教材（数据结构教程 第五版 李春葆主编） 结果发现还是懵逼
事实上，MOOC与书上求得渐进复杂度的方法是不一样的..而且本身题型也不一样
书上的题目是这样的（如下）

#define MAX20
void matrixadd(int n, int A[MAX][MAX], int B[MAX][MAX], int C[MAX][MAX])
{
inti , j;
for(i=0; i<n; i++) //语句①
for(j=0; j<n; j++) //语句②
C[I][J]=A[I][J]+B[I][J];//语句③
}

书上的解法是这样的：

如果不考虑变量定义语句，该算法主要包括三个可执行语句①、②和③。
其中语句①循环控制变量i要从0增加到n，测试i=n时才会终止，故它的频度是n+1，但它的循环体只能执行n次。
语句②作为语句①循环体内的语句应该只执行n次，但语句②本身也要执行n+1次，所以语句②的频度是n(n+1)。
同理可得语句③的频度为n^2(原谅我不会用markdown语法吧）。
因此，该算法中所有语句的频度之和（即执行时间为）
T(n) = n+1+n(n+1)+n^2=2n^2+2n+1

渐进复杂度为O(n^2)

而MOOC上是这么整的（如下）：

for (i=0; i<n; i++)
{
for(j=1, sum=a[0]; j<=i; j++)
sum +=a[j];
cout<<"sum for subarray 0 through"<<i<<"is"<<sum<<endl;
}

T(n)=1+3n+2(1+2+3+4+.......+n-1)=1+3n+n(n-1) =O(n)+O(n^2) =O(n^2)

按照MOOC上老师的说法，是将整个代码块中每一个赋值语句的频数加在一起算得渐进复杂度，即 ：

i=0 => 1次，

i++ => n次，

j=1 => n次，

sum = a[0] =》n次，

j++ => (1+2+3+4+…….+n-1)次，

sum +=a[j] => (1+2+3+4+…….+n-1)次，

ps.最后两个次数相同是因为j<=i，之所以最后是n-1是因为能进入第二个循环的i最大就是n-1。

当我看完MOOC之后试图想用书上的方法解出MOOC上这道题的渐进复杂度，然后我就蒙了

for (i=0; i<n; i++)                //语句①
{  
for(j=1, sum=a[0]; j<=i; j++)   //语句②
sum +=a[j];                        //语句③
cout<<"sum for subarray 0 through"<<i<<"is"<<sum<<endl;

}

T(n)=n+1+n(n-1+1)/2+n(n-1+1)/2=n+1+n^2

结果是比原答案少了个n的，这就很玄幻了

最后在脱发寻求各位大佬之后，我发现了问题的所在，书上在解题是这么说的：

该算法中所有语句的频度之和

哦吼，书上算得是语句，也就是说，实际上是要这么写的：

for (i=0; i<n; i++)                                        //语句①
{  
for(j=1, sum=a[0]; j<=i; j++)                           //语句②
sum +=a[j];                                                //语句③
cout<<"sum for subarray 0 through"<<i<<"is"<<sum<<endl;    //语句④(cout语句) 
}

最后答案也变成了
T(n)=n+1+n(n-1+1)/2+n(n-1+1)/2+n=n+1+n^2+n=O(n^2)

OK,这个少的n就补上来了。

虽然二者的操作不一样，但是本质还是一样的，即用算法其中原操作的执行次数来计量算法的执行时间。
所以说我还是TOO YOUNG TOO SIMPLE.