不知有晋

算法复杂度#

算法复杂度是评价一个算法是否高效的依据。

算法复杂度分为时间复杂度和空间复杂度，一个高效的算法具有用时短或者使用空间少的特点。

随着存储技术的发展，存储介质的容量也发生了翻天覆地的变化，更有出现一些以空间换时间的算法。因此，如今评价算法的效率更加关注“用时短”方面，即是时间复杂度。

时间复杂度#

简单的来说，算法的时间复杂度表示程序运行直至完成所需的总时间。

因为程序可以由不同的程序语言实现，可以在配置不同的机器上面运行，那么不同的程序语言和不同的配置机器之间就没有可比性。因此不能用程序执行的具体时间比较效率，而是要用基本运算的次数来度量算法的时间复杂度。

一个算法是由控制结构（顺序、分支和循环）和原操作（比如有四则运算，比较运算，赋值运算等）构成的，算法时间复杂度取决于两者的基本运算次数之和。进行基本运算的次数越少，其运行时间也就相对越少；基本运算次数越多，其运行时间也就相对越多。

时间复杂度的表示方法#

求解1~1000的累加和：

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <stdio.h>

int main()
{
    int n = 1000;
    int sum = 0;
    for(int i=1;i<=n;i++)
    {
        sum += i;
    }
    printf("sum=%d\t",sum);
    return 0;
}

我们已经知道，算法的时间复杂度取决于算法的基本运算的次数。

以上程序的基本运算次数：$T_n = 3n+3$

算法的时间复杂度通常使用“大O表示法”（ big O notation）表示，大O符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下界。

算法中基本运算次数 $T_n$ 是问题规模 $n$ 的某个函数 $f_n$，记作：$T_n = O(f_n)$。

表示 $T_n$ 与 $f_n$ 是同量级函数，具有相同的增长率；
表示当 $n$ 趋于正无穷时，存在一个常数 $C$ ，总有 $T_n <= C * f_n$ ，
简单的来说，当 $n$ 趋于正无穷时，$T_n = f_n$。

计算时间复杂度#

由 $T_n = 3n + 3$ 可得，
时间复杂度 $O(f_n)=O(3n+3)=O(n)$ 。

计算时间复杂度的步骤：

• 求出问题规模n的基本运算次数函数 $T(n)$
• 只保留函数 $T(n)$ 的最高阶项
• 忽略最高阶项的常数

例如：

$T_n=n^2+3n+4=O(n^2+3n+4)=O(n^2)$

$T_n=4n^2+2n+1=O(4n^2+2n+1)=O(n^2)$

常见的算法时间复杂及其大小#