不知前面所讲的算法的十大特征你是否记住了呢?其实除了这十大特征之外,算法还有两个衡量标准。
不同的问题需要使用不同的算法作为策略,不同的算法也可能占用不同的时间和空间来完成相同的任务,这时候,对算法的选择显得至关重要。一个算法的质量优劣将直接影响整个程序的运行效率。
算法分析的目的是选择合适的算法,并对算法进行改进。如何衡量一个算法的优劣呢?其标准是空间复杂度(Space Complexity)与时间复杂度(Time Complexity)。
一个算法所占用的存储空间包括三个方面:算法本身所占用的空间、输入/输出数据所占用的空间,以及算法运行所占用的空间。
算法本身所占用的空间即程序代码区,用于存放算法程序的二进制代码,与程序的代码行数和各行长度相关。例如以下两段代码,它们实现的功能是一样的,但代码1所占用的空间明显比代码2要多一些。
#输出1~10中3的倍数
#定义test函数:输入任何列表,返回列表中3的所有倍数
def test(x):
list1 = []
for i in x:
if i % 3 == 0: # %是取余运算
list1.append(i)
return list1
#调用test函数计算1~10中3的倍数
print(test(list(range(1,10))))
#使用lambda函数
print(list(filter(lambda x: x % 3 == 0 ,range(1,10))))
由于算法本身所占用的空间很小,所以我们一般不做深究。
输入/输出数据所占用的空间主要是指问题所调用的数据所占用的空间,跟算法没有关系。
算法运行所占用的空间就反映算法的空间复杂度,它是算法运行时所消耗的内存空间的量度,记作:
S
(
n
)
=
O
(
f
(
n
)
)
S(n)=O(f (n))
S(n)=O(f(n))
常见的空间复杂度有 O(1)、0(n)和
O
(
n
2
)
O(n^2)
O(n2)等。
它们分别代表什么意思呢?很简单,当算法运行时占用的临时空间不随某一变量n的改变而改变时,即空间复杂度为常量,表示为 O(1)。同理,当算法运行时占用的临时空间随n的改变而改变时,空间复杂度即O(n);当算法运行时占用的临时空间随n^2的改变而改变时,空间复杂度则为
O
(
n
2
)
O(n^2)
O(n2)以此类推。
空间复杂度是算法运行时所占用空间的一个量度,而不是计算具体的占用空间。