什么是算法复杂度

Taken by iCola

一流程序员靠数学，二流靠算法，三流靠逻辑，四流靠SDK，五流靠Google和StackOverFlow，六流靠百度和CSDN。低端的看高端的就是黑魔法！

对于程序员来说，写一个可以运行的程序肯定是信手拈来，但是如果要求写一个高效的程序，估计有一半以上的程序员得装鸵鸟了。

面试的时候，有些喜欢装X的面试官，明明要找个拧螺丝的，却偏要和被面试者讨论如何造原子弹。比如突然来那么句，某某算法或者某某程序的复杂度是多少？

一、什么是算法复杂度

算法复杂度 (Algorithmic complexity) 简单的讲，就是衡量程序执行效率的度量方法。 衡量算法的好坏，不仅要看程序执行所需的时间，还要看程序用到的计算资源，比如内存资源。 事实上，算法复杂度包括时间复杂度(Time complexity)和空间复杂度(Space complexity)。 我们平时说的算法复杂度，一般都是在说算法的时间复杂度。

二、算法区别能有多大

首先来感受一下什么是好的算法，什么是不好的算法。

计算斐波那契数列第40项的值，可以用如下两种计算方式，代码并不重要，算法主要看思想。

import time


def Fibonacci(n):
assert n > 0, “n > 0”
if (n == 1) or (n == 2):
return 1
return Fibonacci(n – 1) + Fibonacci(n – 2)


def FibonacciImprove(first, second, n):
assert n > 0, “n > 0”
if (n == 1) or (n == 2):
return 1
if (n == 3):
return first + second
return FibonacciImprove(second, first + second, n-1)




def main():
startTime = time.time()
Fibonacci(40)
firstCalcOver = time.time()
print(FibonacciImprove(1,1,40))
secondCalcOver = time.time()
print(firstCalcOver – startTime)
print(secondCalcOver – firstCalcOver)

if __name__ == ‘__main__’:
main()

c:\Python\demo>python Fibonacci.py
35.873504400253296
0.0009908676147460

计算斐波那契第40项的值，使用 Fibonacci 函数的算法，耗时35秒，而使用 FibonacciImprove 函数的算法，耗时不足1毫秒。这就是算法的魅力。

再来看一个具体的例子，在一个从小到大排列的数字中，找到一个给定数字：

从1~9的有序数列中找到8，可以使用以下两种方法：

• 线性查找(Linear search)时，从1开始，需要8次搜索找到目标数字8。

• 二分法查找(Binary search)，第一次找到5，第二次找到7，第三次就可以找到8。

当搜寻的数据明显增加时，比如达到百万级别时，线性查找的速度如果相当于高铁速度的话，那么二分法查找的速度就相当于光速了。

三、时间复杂度

理论上讲，程序执行消耗的时间是无法事先估算的，那如何计算时间复杂度呢？换个思路，程序执行时必然有一定的步骤，不防假设执行每个步骤所需要的时间为t，t具体是什么值并不重要，然后只需要计算一个程序执行所需要的步骤，最终以步骤数来衡量算法时间复杂度。

举个例子，计算1+2的复杂度是多少呢？

a = 1
b = 2
sum = a + b

一共有3个步骤，不防记作O(3)，其实O(3) = O(1)。

计算正整数n的阶乘呢？

factorial = 1
for i = 1 to n
factorial = i * factorial

第一行执行1次，第二行执行n次 ，第三行执行n次，一共执行 2n + 1 次。不防记作O(2n + 1)。其实O(2n + 1) = O(n)。

四、大O表示法

现在可以很自然的引入大O表示法了(Big O notation)。为什么用O呢？其实这里的O源自短语函数的阶数(Order of the function)。

如果还记得高数中等价无穷小和等价无穷大的概念的话，就很容易理解大O表示法了。

不难理解，当x趋于∞时，对f(x)值变化影响最大的是x³，那么我们就可以说f(x)和 x³ 是等价无穷大的。因此，常数次执行步骤的算法复杂度统称为O(1)，这也是为什么前面我说 O(3) = O(1) 。类似的， O(2n + 1) = O(n) 。

计算算法时间复杂度时，我们只需要关心对结果影响最大的那一项，也就是直接找到计算结果等价无穷大最简洁的表示方法。因此我们可以推导出O(f(x)) = O( x³ )。

大O表示法其实是在描述一个算法在遇到最糟糕的情况时执行的效率。

想象一下唐伯虎点秋香场景，从n个蒙面女生中点中秋香，最好的情况是第一次就点中秋香，最坏的情况则需要n次。这里，我们就认为找秋香的算法复杂度是O(n)。

有了以上的基础，我们就很容易理解下面这些常见的算法复杂度了。

常见的复杂度曲线对比：

举个O(n²)复杂度的例子，这里不使用具体的编程语言，而使用通俗易懂的伪码(Pseudocode)：

get a positive integer from input
if n > 10
print “This might take a while…”
for i = 1 to n
for j = 1 to i
print i * j

print “Done!”

对于复杂度O(n!)，最著名的例子就是旅行推销员问题(Travelling salesman problem, TSP)：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题。解决这类问题没有什么好的算法，只能遍历所有可能解，然后比较各个解的优越性。对于TSP问题，第一次选择可以有n个，选定了第一个城市后，第二个城市的选择则有n-1个，以此类推，总共会有n!种不同的组合。因此，这类问题的算法复杂度是O(n!)。

空间复杂度这里就不多介绍了，想进一步了解，后台回复『 复杂度 』阅读文章《大O表示法扩展阅读》。

五、小结

算法复杂度包括时间复杂度和空间复杂度，时间复杂度用于衡量最糟糕情况下程序的执行效率。

计算时间复杂度时，只需要关注影响计算结果最大的那一项，通常就是表达式中最高次方项。

大O表示法是衡量算法复杂度常用的表示方法，学习任何算法都避不开算法复杂度的计算。

推荐：

推荐阅读：5G 是什么

后台回复『 复杂度 』阅读文章《大O表示法扩展阅读》。

喜欢就 『 关注 』或者『 分享 』吧。