算法时间复杂度和空间复杂度
算法,即解决问题的方法。同一个问题,使用不同的算法,虽然得到的结果相同,但是耗费的时间和资源是不同的。
就比如要拧一个螺母,使用扳手还是钳子是有区别的,虽然使用钳子也能拧螺母,但是没有扳手好用。
“条条大路通罗马”,解决问题的算法有多种,这就需要判断哪个算法“更好”。
例如,要解决依次输出一维数组中的数据元素的值的问题,首先想到的是使用循环结构( for 或者 while ),在有这个算法的基础上,开始编写程序。
所以,算法相当于是程序的雏形。当解决问题时,首先心中要有解决问题的算法,围绕算法编写出程序代码。
例如拧螺母,扳手相对于钳子来说更好使(选择算法的过程),但是在拧的过程(编写程序的过程)中发现螺母生锈拧不动,这时就需要另想办法。
为了避免这种情况的发生,要充分全面地思考问题,尽可能地考虑到所有地可能情况,慎重选择算法(需要在实践中不断地积累经验)。
如果准确性和健壮性都满足,接下来,就要考虑最重要的一点:通过算法编写的程序,运行的效率怎么样。
运行效率体现在两方面:
好算法的标准就是:在符合算法本身的要求的基础上,使用算法编写的程序运行的时间短,运行过程中占用的内存空间少,就可以称这个算法是“好算法”。
在学习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 次。
如果a、b、c组成一段程序,那么算法的时间复杂度为
简化的过程总结为3步:
所以,最终a、b和c合并而成的代码的时间复杂度为
谷歌浏览器相比于其他的浏览器,运行速度要快。是因为它占用了更多的内存空间,以空间换取了时间。
算法中,例如判断某个年份是否为闰年时,如果想以时间换取空间,算法思路就是:当给定一个年份时,判断该年份是否能被4或者400整除,如果可以,就是闰年。
如果想以空间换时间的话,判断闰年的思路就是:把所有的年份先判断出来,存储在数组中(年份和数组下标对应),如果是闰年,数组值是1,否则是0;当需要判断某年是否为闰年时,直接看对应的数组值是1还是0,不用计算就可以马上知道。
就比如要拧一个螺母,使用扳手还是钳子是有区别的,虽然使用钳子也能拧螺母,但是没有扳手好用。
“条条大路通罗马”,解决问题的算法有多种,这就需要判断哪个算法“更好”。
算法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”记法
。
注意,是大写的字母对于上边的例子而言,a 的时间复杂度为O
,不是数字0
。
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,去掉系数。(n2 系数为 1)
所以,最终a、b和c合并而成的代码的时间复杂度为
O(n2)
。
常用的时间复杂度的排序
列举了几种常见的算法时间复杂度的比较(又小到大):O(1)常数阶
< O(logn)对数阶
< O(n)线性阶
< O(n2)平方阶
< O(n3)(立方阶)
< O(2n) (指数阶)
拿时间换空间,用空间换时间
算法的时间复杂度和空间复杂度是可以相互转化的。谷歌浏览器相比于其他的浏览器,运行速度要快。是因为它占用了更多的内存空间,以空间换取了时间。
算法中,例如判断某个年份是否为闰年时,如果想以时间换取空间,算法思路就是:当给定一个年份时,判断该年份是否能被4或者400整除,如果可以,就是闰年。
如果想以空间换时间的话,判断闰年的思路就是:把所有的年份先判断出来,存储在数组中(年份和数组下标对应),如果是闰年,数组值是1,否则是0;当需要判断某年是否为闰年时,直接看对应的数组值是1还是0,不用计算就可以马上知道。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频