数据结构与算法学习

时间复杂程度

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

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

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

#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
        }
}

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

上题

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

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

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

外层 循环结束的条件是 ，所以外层循环 次

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

即时间复杂度就是 （这里的 是当外层循环到第 次的时候内层 循环次数）

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

求和公式安排

将 替换为，求解就是

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

则时间复杂度 ，即