算法复杂度这一篇就够了

什么是算法的复杂度？

时间复杂度

时间复杂度指的就是这个程序需要计算的工作量

通常的说，这个算法的指令数越多，需要的时间就越长。一个算法中的语句执行次数称为语句频度，记为T(n)。时间复杂度记作：T(n)=O(f(n))。 这样用 O 来表示算法时间复杂度的方法我在下面会详细讲。n越来越大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的时间复杂度。f(n)是问题规模 n 的某个函数。
一般情况下 ，随着 n 的增大，T(n) 增长最慢的算法为最好的算法。

空间复杂度

空间复杂度指的就是这个算法运行时临时占用电脑储存空间的大小。

时间复杂度和空间复杂度并称为算法的复杂度。

O表示法

你可能听说过某某算法的复杂度是 O(n²)，这就是 O表示法。

假设 a 是一个二维数组，O(n²) 的代码表示为：

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
	cout<<a[i][j];
    }
}
1
2
3
4
5

每个算法在不同情况下的复杂度也不同，比如冒泡排序，它在最好的情况下比较一轮就可以完成排序，最坏情况下需要执行完两层循环才能完成排序。所以，我们把算法复杂度从最好情况、平均情况和最坏情况三个角度来评价。 而 O 表示法表示的是算法的最坏情况。

推导算法复杂度的方法

①：用1代替运行时间中的所有加法常数。

②： 在执行完 ① 后的运行次数函数中，只保留最高阶项。

③： 如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。

常数阶

看这个代码

int a = 12,b = 18,num; //运行次数+1
num = a+b; //运行次数+1
cout<<num; //运行次数+1
1
2
3

很显然，这段代码用来计算 a+b。

我们来推导一下它的复杂度。

我们这里的运行时间 (也就是次数)是 f(n)=1+1+1=3，这就叫加法常数，我们把它变成1。这里没有最高阶项（最高阶项就是未知数的指数最高的项，因为1这一项没有未知数，算作加法常数），直接得到结果，算法复杂度为O(1)。我们称这样的复杂度为 O(1) 的算法为常数阶。

注意，只要 f(n) 是一个整数，不管它是 2，是 4 还是几，这个时间复杂度只能是 O(1)，因为这些加法常数都要变成1。

平方阶

现在你知道了推导规则，你基本可以推导大部分程序的时间复杂度。

我再来举个复杂点的例子，就是一开始我举那个例子，我推一下它的复杂度。

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
	cout<<a[i][j];
    }
}
1
2
3
4
5

首先，这是两层循环，外层循环执行 n 次，内层循环执行 n 次。

这里我要讲到一个乘法原则：嵌套循环的时间复杂度 = 内层循环执行次数 × 外层循环执行次数。

所以，这个循环嵌套的时间复杂度就是 O(n²)。

主定理

大家可能听说过递推算法，一些递推算法可以表示为 T(n) = aT(n/b)+f(n)。

其中 a>=1，b>1，f(n)是递推式以外的式子，可以是未知数和常数。

遇到这种情况，我们要计算出以b为底的a的对数。比如 b 的 x 次方等于 a，则称x是以b为底的a的对数。

我们还需要计算出 f(n) 的指数。需要注意1的指数是0，因为任何整数的0次方都等于1。还需要注意，sqrt(n)（也就是根号下n）的指数为1/2。

我们把 f(n)的指数和以b为底的a的对数比较，

如果他们相等，则这个算法的时间复杂度是 n的以b为底的a的对数次方×log f(n)。

如果 f(n)的指数大于以b为底的a的对数，则该算法复杂度为 O(f(n))

如果 f(n)的指数小于以b为底的a的对数，则该算法复杂度为 O(n的以b为底的a的对数次方)

完美结束

好的，这样就结束了呢，有错误请评论指正。