时间复杂度

算法时间复杂度常用大O记法，记作O(x)，x为大O阶。

默认情况下，我们分析一段程序的时间复杂度，应该是指它的最坏时间复杂度（最坏的情况下，耗时最长）。

推导大O阶

由于运行次数函数中起主导作用的是最高次项，因此若代码出现了循环结构，则其最高次项肯定不为1，所以计算时间复杂度时，完全可以忽略时间复杂度为O(1)的语句（包括循环内的逻辑判断、计数的语句，因为它们无非就是增加高次项的系数），重点在循环结构等耗时的部分上。

1
2
3


int a = 0;
sum = a + 1;
printf("%d", sum)

运行次数函数为f(n)=3，时间复杂度为O(1)。

1
2
3
4
5


int i;
for(i=0; i < n; i++)
{
    //时间复杂度为O(1)的代码
}

时间复杂度为O(n)。

1
2
3
4
5
6


int i = 1;
while(i < n)
{
    i = i * 2;
    //时间复杂度为O(1)的代码
}

设循环运行的次数为x，则$2^x = n$，即循环次数为$log_2^n$，我们把它的时间复杂度记作O(logn).

1
2
3
4
5
6
7
8


int i, j;
for(i = 0; i < n; i++)
{
    for(j = 0; j < n; j++ )
    {
        //时间复杂度为O(1)的代码
    }
}

上述时间复杂度为O($n^2$).

1
2
3
4
5
6
7
8


int i, j;
for(i = 0; i < m; i++)
{
    for(j = 0; j < n; j++ )
    {
        //时间复杂度为O(1)的代码
    }
}

上述时间复杂度为O($m\times n$).

结论：循环的时间复杂度等于循环体内的时间复杂度乘以循环次数。

1
2
3
4
5
6
7
8


int i, j;
for(i = 0; i < n; i++)
{
    for(j = i; j < n; j++ )
    {
        //时间复杂度为O(1)的代码
    }
}

当i=0，内层循环将进行n次；当i=1，内层循环将进行(n-1)次；当i=n-1，内层循环将进行1次。所以总的执行次数为 $$n+(n-1)+...+1=\frac {n(n+1)}2$$ 上述时间复杂度为O($n^2$)