算法(algorithm)本质上是一连串的计算。同一个问题可以使用不同算法解决,但计算过程中消耗的时间和资源可能千差万别。那如何比较不同算法之间的优劣呢?
目前分析算法主要从时间和空间两个维度进行。时间维度就是算法需要消耗的时间,时间复杂度(time complexity)是常用分析单位。空间维度就是算法需要占用的内存空间,空间复杂度(space complexity)是常用分析单位。
因此,分析算法主要从时间复杂度和空间复杂度进行。很多时候二者不可兼得,有时用时间换空间,有时用空间换时间。
1. 时间复杂度 Time Complexity
现代硬件性能强大,即使是非常昂贵的算法,数据量小时速度也可能很快。但数据量变大时,时间开销就会明显变大。时间复杂度是随着数据量增加,算法耗费时间的度量单位。
1.1 常数时间 Contant Time
常数时间算法不会随数据量变化而变,时间固定。
查看下面方法:
func checkFirst(names: [String]) {
if let first = names.first {
print(first)
} else {
print("No Names")
}
}
该函数执行所需时间与 names 数组大小无关。无论数组有十个元素,还是一万个元素,该函数都只检查数组第一个元素。
下图是数据量与时间关系图: