数据结构与算法学习

时间复杂程度

首先我们看看啥是时间复杂程度

一般情况下，算法中基本操作重复执行的时间是问题规模 $n$ 的某个函数 $f(n)$，算法的渐进时间复杂度（简称时间复杂度（Time Complexity））记为
$$
T(n) = O[f(n)]
$$

它表示随问题规模 $n$ 的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，$f(n)$ 一般是算法中频度最大的语句频度。

#define n 自然数
void Matrixmlt(int A[n][n],int B[n][n],int C[n][n])
{
    int i,j,k;
    for(i=0;i<n;i++)                          //语句①        n+1
        for(j=0;j<n;j++)                      //语句②        n(n+1)
        {
            C[i][j]=0;                        //语句③        n*n
            for(k=0;k<n;k++)                  //语句④        n*n(n+1)
                C[i][j]=C[i][j]+A[i][k]*B[k][j];   //语句⑤   n*n*n
        }
}

由此可见，当有循环嵌套时，算法的时间复杂度是由最内层语句的频度 $f(n)$ 决定的

上题

计算以下程序段的时间复杂度

for(i=1;i<=n;i++)
{
    s=0;
    j=1;
    while(s<=n)
    {
        j++;
        s=s+j;
    }
}

由上述知识我们可以知道，这里计算时间复杂度是计算最内层的 $while$ 循环的频度

外层 $for$ 循环结束的条件是 $i<=n$，所以外层循环 $n$ 次

内层 $while$ 循环结束条件是 $s<=n$，巧妙就巧妙在这个 $s$ 这里，我一开始还没发现（其实是太菜了而且有一段时间没有接触C语言了）

即时间复杂度就是 $n*f(n)$（这里的 $f(n)$ 是当外层循环到第 $n$ 次的时候内层 $while$ 循环次数）

$s$ 初始值为 $0$，$while$ 每循环一次，$j$ 自增并且 $s=s+j$，那么 $s$ 就可以看作是求所有 $while$ 循环中 $j$ 的和

$$ s=2+3+4+5+…+j-1+j $$

求和公式安排

$$ \frac{(j+2)(j-1)}{2}\leq n $$

将$j$ 替换为$f(n)$，求$f(n)$解就是

$$ \frac{(f(n)+2)(f(n)-1)}{2} = n $$

解方程（时间复杂度不能为负）

$$ f(n) = \frac{-1 + \sqrt{8n + 9}}{2} $$

则时间复杂度 $T(n)=O(n*f(n))$ ，即

$$ T(n) = O\left [ \left (\frac{-1\pm \sqrt{8n+9}}{2} \right )\cdot n\right ] = O(n^{\frac{3}{2}}) $$