算法复杂度这一篇就够了

什么是算法的复杂度?

时间复杂度

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

通常的说,这个算法的指令数越多,需要的时间就越长。一个算法中的语句执行次数称为语句频度,记为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];
    }
}

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

推导算法复杂度的方法

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

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

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

常数阶

看这个代码

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

很显然,这段代码用来计算 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];
    }
}

首先,这是两层循环,外层循环执行 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的对数次方)

完美结束

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

你可能感兴趣的