一旦开始翻译就根本停不下来。

翻译自swift-algorithm-club 


知道算法有多快以及占用多少内存是非常有用的，能够帮助你选择合适的算法。

算法复杂度给你一个粗略的关于算法运行时间和占用内存的指示，当某人说这个算法最多O(n^2)的运行时间和O(n)的内存，就表示这个算法有点慢但并不暂用很多内存。

通常通过数学分析来计算算法复杂度，这里不详细介绍如何计算，但是知道这些符号的意义还是很重要的。

符号
  
描述
O(1)
  
最优，这种类型的算法经常消耗同样多的时间，不管有多少数据，例如从数组中查找一个元素的索引
O(log n)
  
非常好，这种类型的算法不同的元素数量消耗的时间不同，如果你有100个item，需要7次来得到答案，如果是1000个，需要10次，如果1000000需要20测，比较适合数量较多的元素。例如折半查找。
O(n)
  
比较好 如果你有100个item，那需要100次搜索，如果200个 则需要200次搜索。例如顺序查找。
O(nlog n)
  
比（n）差，例如快速排序
O(n^2)
  
有点慢，如果你有100个item，需要100*100次，两倍的item会比慢4倍（2 * 2 = 4）,插入排序。
O(n * 3)
  
差，例如 矩阵乘法
O(2 ^ n)
  
非常差,你可能想要避免这种算法，但是有时候你别无选择。例如：旅行商问题
O(n!）
  
极慢,需要花几百年。
通常你只需要用直觉就能算出算法复杂度，如果你的代码使用一0个n的元素简单的循环，那么复杂度就是O(n),如果有2个相连的循环，那就是O(n^2),三个就是O(n^3)等等。

注意复杂度只是一个简单的估计而且只有当基数非常大时，例如，插入排序的最差结果是O(n^2),理论上它会比快速排序O(nLogn)慢,但是如果是一小部分数量，插入排序明显要快，尤其是当这个数组本身已经是有序的。

如果你觉得这个有点困惑，别让复杂度困惑太多。它通常在比较两个算法时有用，但是最终你只有测试才知道哪一个更好。而且如果基数确实很小，那么即便是慢的算法也会比快的算法更适合。

O（大O）：表示小于等于

o（小o）：表示小于

Ω（大欧米嘎）：大于等于

ω（小欧米嘎）：大于

Θ：等于

常用的表示复杂度的符号有O、Ω、Θ和o，下面用通俗的语言解释一下这些符号的含义。


用T(n)表示一个算法输入规模为n的时候的复杂度。复杂度分析里比较两个多项式f(x)和g(x)是比较其增长速度，用专业说法就是：


如果存在正常数c和k，使得当n≥k时，f(x)≥cg(x)，则说明f(x)增长比g(x)快。反之亦然。


然后O的含义是复杂度上界，即存在正常数c和k，使得当n≥k时，T(n)≤cf(n)，则T(n)=O(f(n))。然后Ω表示复杂度下界，就是存在正常数c和k，使得当n≥k时，T(n)≥cf(n)，则T(n)=Ω(f(n))。


然后如果T(n)=O(f(n))且T(n)=Ω(f(n))，则T(n)=Θ(f(n))。

最后是o，如果T(n)=O(f(n))且，T(n)≠Θ(f(n))，则T(n)=o(f(n))，也就是表示更松的上界（一般不用吧……）

注解：sup是单词supremum的简写，意思是最小上界。inf是单词infimum的简写，意思是最大下界。

数学中，经常出现的表示方式是 lim sup 或者 lim inf，即找上界或者下界的极限。