算法时间复杂度和空间复杂度

算法,即解决问题的方法。同一个问题,使用不同的算法,虽然得到的结果相同,但是耗费的时间和资源是不同的。

就比如要拧一个螺母,使用扳手还是钳子是有区别的,虽然使用钳子也能拧螺母,但是没有扳手好用。

“条条大路通罗马”,解决问题的算法有多种,这就需要判断哪个算法“更好”

算法VS程序

很多人误以为程序就是算法,其实不然:算法是解决某个问题的想法、思路;而程序是在心中有算法的前提下编写出来的可以运行的代码。

例如,要解决依次输出一维数组中的数据元素的值的问题,首先想到的是使用循环结构( for 或者 while ),在有这个算法的基础上,开始编写程序。

所以,算法相当于是程序的雏形。当解决问题时,首先心中要有解决问题的算法,围绕算法编写出程序代码。

有算法一定能解决问题吗?

对于一个问题,想出解决的算法,不一定就能解决这个问题。

例如拧螺母,扳手相对于钳子来说更好使(选择算法的过程),但是在拧的过程(编写程序的过程)中发现螺母生锈拧不动,这时就需要另想办法。

为了避免这种情况的发生,要充分全面地思考问题,尽可能地考虑到所有地可能情况,慎重选择算法(需要在实践中不断地积累经验)。

“好”算法的标准

对于一个问题的算法来说,之所以称之为算法,首先它必须能够解决这个问题(称为准确性)。其次,通过这个算法编写的程序要求在任何情况下不能崩溃(称为健壮性)。

如果准确性和健壮性都满足,接下来,就要考虑最重要的一点:通过算法编写的程序,运行的效率怎么样。

运行效率体现在两方面:
  • 算法的运行时间。(称为“时间复杂度”
  • 运行算法所需的内存空间大小。(称为“空间复杂度”

好算法的标准就是:在符合算法本身的要求的基础上,使用算法编写的程序运行的时间短,运行过程中占用的内存空间少,就可以称这个算法是“好算法”。
调查表明,人们对于软件或者 APP 的运行效率有极高的要求,例如对于网页打开的忍耐极限是 6 秒甚至更短,如果你设计的网页打开的时间超过 6 秒,多数人会在 4 秒甚至 3 秒的时候毫不犹豫地关掉而去浏览其他网页。在这个大背景下,一个好的“算法”更注重的是时间复杂度,而空间复杂度只要在一个合理的范围内就可以。

时间复杂度的计算

计算一个算法的时间复杂度,不可能把所有的算法都编写出实际的程序出来让计算机跑,这样会做很多无用功,效率太低。实际采用的方法是估算算法的时间复杂度。

在学习C语言的时候讲过,程序由三种结构构成:顺序结构、分支结构和循环结构。顺序结构和分支结构中的每段代码只运行一次;循环结构中的代码的运行时间要看循环的次数。

由于是估算算法的时间复杂度,相比而言,循环结构对算法的执行时间影响更大。所以,算法的时间复杂度,主要看算法中使用到的循环结构中代码循环的次数(称为“频度”)。次数越少,算法的时间复杂度越低。

例如:
a) ++x; s=0;
b) for (int i=1; i<=n; i++) { ++x; s+=x; }
c) for (int i=1; i<=n; i++) { for (int j=1; i<=n; j++) { ++x; s+=x; } }

上边这个例子中,a 代码的运行了 1 次,b 代码的运行了 n 次,c 代码运行了 n*n 次。

时间复杂度的表示

算法的时间复杂度的表示方式为:
O(频度)
这种表示方式称为大“O”记法
注意,是大写的字母O,不是数字0
对于上边的例子而言,a 的时间复杂度为O(1),b 的时间复杂度为O(n),c 的时间复杂度为为O(n2)

如果a、b、c组成一段程序,那么算法的时间复杂度为O(n2+n+1)。但这么表示是不对的,还需要对n2+n+1进行简化。

简化的过程总结为3步:
  • 去掉运行时间中的所有加法常数。(例如 n2+n+1,直接变为 n2+n)
  • 只保留最高项。(n2+n 变成 n2
  • 如果最高项存在但是系数不是1,去掉系数。(n系数为 1)

所以,最终a、b和c合并而成的代码的时间复杂度为O(n2)

常用的时间复杂度的排序

列举了几种常见的算法时间复杂度的比较(又小到大):
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)

拿时间换空间,用空间换时间

算法的时间复杂度和空间复杂度是可以相互转化的。

谷歌浏览器相比于其他的浏览器,运行速度要快。是因为它占用了更多的内存空间,以空间换取了时间。

算法中,例如判断某个年份是否为闰年时,如果想以时间换取空间,算法思路就是:当给定一个年份时,判断该年份是否能被4或者400整除,如果可以,就是闰年。

如果想以空间换时间的话,判断闰年的思路就是:把所有的年份先判断出来,存储在数组中(年份和数组下标对应),如果是闰年,数组值是1,否则是0;当需要判断某年是否为闰年时,直接看对应的数组值是1还是0,不用计算就可以马上知道。