我们都知道算法是处理数据的方法,那么如何衡量一个算法的好坏呢?(即,判断该算法的效率如何) 由于算法在编写成可执行程序后,运行会消耗时间资源和空间(内存)资源,因此衡量一个算法的好坏一般通过时间和空间两个维度进行衡量。即,时间复杂度和空间复杂度。
时间复杂度是衡量一个算法运行的快慢。
找到某条基本语句与问题n之间的数学函数关系,就是找到了算法的时间复杂度。即,算法的时间复杂度本质上是一个数学的函数表达式。
如果是第一次听说算法的时间复杂度,应该会片面的认为是计算一个算法运行所需要的时间。然而实际上由于机器的性能不同,以及一些不可控因素影响,一个算法运行的具体时间是无法计算出的(即,同一个算法在不同编译器上运行的时间是不一定相同的)。 那么我们该如何衡量一个算法的运行快慢呢?我们注意到算法的运行时间与算法中语句的执行次数是成正比例的,因此我们就把算法中基本操作的执行次数作为算法的时间复杂度。
先看一个题(注释中标注了语句的执行次数)。
// 请计算一下Func1中++count语句总共执行了多少次?
void Func1(int N) //N*N + 2*N + 10
{
int count = 0;
for (int i = 0; i < N; ++i) //N*N
{
for (int j = 0; j < N; ++j) //N
{
++count;
}
}
for (int k = 0; k < 2 * N; ++k) //2*N
{
++count;
}
int M = 10;
while (M--) //10
{
++count;
}
printf("%d\n", count);
}
我们不难计算出,Func执行的基本操作的次数为: F(N) = NN+2N+10 N = 10 F(N) = 130 N = 100 F(N) = 10210 N = 1000 F(N) =1002010 可以看到当N 越大,后面两项对总数的影响就越小,N无限大时,后面两项可以忽略不计。 因此实际计算时,我们不一定要计算精确的执行次数,只需要一个大概的估算即可表示算法的时间复杂度即可。
1.大O符号(Big O notation):是用于描述函数渐进行为的数学符号。 大O的渐进表示法:(规则) 1.用常数1代替运行时间中所以加法常数 2.在修改后的运行次数中只保留最高次数项 3.如果最高次数项存在,并且不是1,则去除与最高次数项的系数
用大O的渐进表示法可以大致的表示出算法的大概量级。 可以直接看出,用大O渐进表示法以后,Func的时间复杂度为O(n^2)。
有一些算法存在:最坏情况、最好情况和平均情况。 例如,在N个数中找最大的数 我们很容易知道,最坏情况是找n次,平均情况找n/2次,最好情况找1次 但是实际中,一般关注最坏运行情况(悲观保守的预估),因此这个查找的方法时间复杂度为O(n)。
计算时间复杂度时会出现有以二为底n的对数这种情况,具体有以下两种表示(图中绿色框里的)
一般情况下的对数都是以2为底的对数,所以简写也只针对以2为底。其他底数的对数形式没有简写,也很少出现。
空间复杂度是衡量一个算法运行所需要额外开辟的空间
本质上也是一个函数表达式,用来计算算法的空间效率
1.首先,空间复杂度计算的不是程序在运行过程中总共开辟的空间,而是临时(额外)开辟的空间(所谓额外,就是指不包括原有的空间)只需要计算这个算法所需要的额外空间即可。 2.其次,空间复杂度不是计算不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。
注意: 1.函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运的得时候申请的额外空间来确定。 2.在栈区或者堆区开辟的额外空间都要计算上。
空间复杂度计算规则基本跟时间复杂度类似,也是使用大O渐进表示法,只需要计算出它大概属于哪个量级即可。(时间复杂度中已经介绍过大O的渐进表示法,这里就不再赘述了)
实际上,目前我们更关注时间复杂度,不太关注空间复杂度,原因可以参考摩尔定律。因为目前的机器内存空间都比较大,所有可以不太注重(但是也不能耗费太多)。 摩尔定律:摩尔定律是英特尔创始人之一戈登·摩尔的经验之谈,其核心内容为:集成电路上可以容纳的晶体管数目在大约每经过18个月到24个月便会增加一倍。换言之,处理器的性能大约每两年翻一倍,同时价格下降为之前的一半。
例子 | 复杂度(大O渐进表示法) | 量级 |
---|---|---|
5201314 | O(1) | 常数阶 |
3n+4 | O(n) | 线性阶 |
3n^2+4n+5 | O(n^2) | 平方阶 |
3logn+4 | O(logn) | 对数阶 |
2n+3nlogn+14 | O(nlogn) | nlogn阶 |
n^3+2n+6 | O(n^3) | 立方阶 |
2^n | O(2^n) | 指数阶 |
对比图如下:
可以看出时间复杂度虽然不能直接表示出算法运行所需的时间,但是可以对比出不同算法的效率高低。
1.计算时间复杂度不能直接数循环,要根据算法的逻辑来计算。 2.空间是可以重复利用的,不用累计;(递归过程中/循环过程中,一些在栈区开辟的空间经过函数栈帧的创建与销毁,这些空间是可以重复利用的) 而时间是一去不复返的,需要累计。(时间是不能重复利用的)
以上就是今天要讲的内容,本文主要介绍了衡量一个算法好坏的方法,即算法的时间复杂度和空间复杂度,同时还介绍了如何计算复杂度以及一些常见复杂度的对比。 本文作者也是一个正在学习编程的萌新,目前也只是刚开始接触数据结构这方面的内容,如果有什么内容方面的错误或者不严谨,欢迎大家在评论区指出。 最后,如果本篇文章对你有所启发的话,也希望可以支持支持作者,谢谢大家!