前言
一个算法的好坏,我们该如何衡量呢?在算法领域是用时间与空间来衡量的。
我们通常根据算法的复杂度来衡量一个程序设计。复杂度分为时间复杂度、空间复杂度,接下来我们就讨论下什么怎么计算时间复杂度与空间复杂度。
时间复杂度
时间复杂度,一个方法或者程序重复执行计算的时间工作量。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用”O”来表示数量级,给出算法的时间复杂度。
T(n)=O(f(n)) 简称推导大O阶法
它表示随着问题规模的n的增大,算法的执行时间的增长率和f(n)的增长率相同,这称作算法的渐进时间复杂度,简称时间复杂度。而我们一般讨论的是最坏时间复杂度,这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,分析最坏的情况以估算算法指向时间的一个上界。
按增量递增复杂度排列时间从小到大依次是:
常数阶
O(1)
不管当n是多少,只运行2次,那么时间复杂度就是
O(2)
,取为O(1)
。这个算法的运行次数函数是f(n) = 2
.根据我们推导的大O阶的方法,第一步就是把常数项2改为1,。在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的时间复杂度为O(1)
。1
2
3
4
5
6
7
8
9
10
11
12def constantTime(): Unit ={
//时间复杂度O(1)
var sum = 0
val n = 1000
/*执行一次*/
sum = (1 + n) * n / 2;
/*执行一次*/
sum = (1 + n) * n / 2;
printf("%d",sum);
}对数阶
O(log2n)
由于每次count乘以2之后,就距离n更近了一分。也就是说,有多少个2相乘后大于n,则会退出循环。由2的x次方=n,得到
x=log₂n
。所以这个循环的时间复杂度为O(logn)
。1
2
3
4
5
6
7
8def log2n(): Unit ={
//时间复杂度O(log2n)
var count = 1
val n = 1000
while(count < n){
count *= 2
}
}线性阶
O(n)
线性阶的循环结构会复杂很多。要确定某个算法的阶次,我们常常需要确定某个特定语句或某个语句集运行的次数。因此,我们要分析算法的复杂度,关键就是要分析循环结构的运行情况。
下面这段代码,它的循环的时间复杂度为O(n)
,因为循环体中的代码必须要执行n次。1
2
3
4
5
6
7def n(): Unit ={
//时间复杂度O(n)
val n = 1000
for (i <- 1 until n){
printf("%d ",i);
}
}线性对数阶
O(n * log2n)
下面这段代码,它的循环的时间复杂度为
O(n)
,但是循环里面有又有一个对数阶O(log2n)
,因为循环体中的代码必须要执行n * log2n
次,即它的最终时间复杂度O(n * log2n)
1
2
3
4
5
6
7
8
9
10
11def nlog2n(): Unit ={
//时间复杂度O(n * log2n)
val n = 1000
for (i <- 1 until n){
var count = 1
while(count < n){
count *= 2
printf("%d ",i);
}
}
}平方阶
O(n^2)
两次循环,里面循环执行了n次,外层循环也执行了n次,所以时间复杂度为
O(n^2)
,立方阶一样1
2
3
4
5
6
7
8
9def n2(): Unit ={
//时间复杂度O(n^2)
val n=10
for (i <- 0 until n){
for(j <- 0 until n){
printf("%d", i)
}
}
}立方阶
O(n^3)
三次循环,里面循环执行了n次,外层循环也执行了n次,所以时间复杂度为
O(n^3)
,立方阶一样1
2
3
4
5
6
7
8
9
10def n3(): Unit ={
//时间复杂度O(n^3)
val n=10
for (i <- 0 to n){
for(j <- 0 to n){
for(k <- 0 to(n))
printf("%d", i)
}
}
}
空间复杂度
算法需要消耗的内存空间。即为S(n)=O(f(n))
;包括程序代码所占用的空间,输入数据所占用的空间和辅助变量所占用的空间这三个方面。计算和表达方式与时间复杂度类似,一般用复杂度的渐近性来表示。我们在写代码的时候,完全可以用空间来换取时间,比如说,数据库的索引,都是在元数据的基础上构建庞大的索引存储,已达到提供查询的效率,又或者数据库表设计冗余字段等都是已空间来换取时间到达目的。
关于
O(1)
的问题,O(1)
是说数据规模和临时变量数目无关,并不是说仅仅定义一个临时变量。举例:无论数据规模多大,我都定义100个变量,这就叫做数据规模和临时变量数目无关。就是说空间复杂度是O(1)
。
总结
代码示例地址
https://github.com/lishijia/algorithm/tree/master/src/main/scala/lishijia/algorithm
算法时间空间复杂度汇总