知道算法有多快以及需要多少空间是非常有用的。 才能为你的工作选择正确的算法。
O表示法给你一个算法的运行时间和它使用的内存量的粗略表示。 当有人说，“这种算法最糟糕的运行时间是O（n ^ 2），使用O（n）空间”。意思是它很慢，但不需要大量额外的内存。
计算算法的O通常通过数学分析来完成。 我们跳过这里的数学，但是了解不同的值意味着什么是有用的，所以这里是一个方便查阅的表。 n指您正在处理的数据项数。 例如，当对100个项目的数组进行排序时，n = 100。
| 大O | �名字 | �说明 |
|---|---|---|
| O(1) | �常量 | 这是最好的。 该算法不管有多少数据，总是花费相同的时间。 示例：通过索引查找数组的元素。 |
| O(log n) | 对数 | 特别好。 该算法将每次迭代的数据量减半。 如果你有100个元素，它需要大约7个步骤来找到答案。 有1000个，需要10个步骤。 100万个只需要20步。 即使对于大量的数据，这也是超快的。 示例：二进制搜索。 |
| O(n) | 线性 | 很好。 如果你有100个元素，需要100个步骤。 元素个数增加一倍，该算法花费的时间会是两倍。 示例：顺序搜索。 |
| O(n log n) | 线性代数 | 体面的表现。 这比线性稍差，但不太差。 示例：最快的通用排序算法。 |
| O(n^2) | 二次 | 有点慢。 如果你有100个元素，要执行100 ^ 2 = 10,000步骤。 加倍的元素数量使其慢四倍（因为2平方等于4）。 示例：使用嵌套循环的算法，如插入排序。 |
| O(n^3) | �三次 | 很慢。 如果你有100元素，会是100 ^ 3 = 1,000,000步骤。 输入大小加倍使其慢8倍。 示例：矩阵乘法。 |
| O(2^n) | 指数 | 特别慢。 你想避免这些算法，但有时你没有选择。 添加一个元素就会使运行时间加倍。 示例：旅行推销员问题 |
| O(n!) | 阶乘 | 无法忍受的慢。 一百万年也运行不完。 |
通常你不需要数学方式计算一个算法的�大O，但你可以简单地使用你的直觉。 如果你的代码使用一个循环，看看你的输入的所有n个元素，算法是 O(n) 。 如果代码有两个嵌套循环，它是 O(n ^ 2) 。 三个嵌套循环给出 O(n ^ 3) ，等等。
上面的表示法是一个估计，只对较大数量的元素真正有用。 例如，插入排序算法的最坏情况运行时间是 O(n ^ 2) 。 在理论上比合并排序的最坏情况运行时间是 O(n log n) 。 但对于少量的数据，插入排序实际上更快，特别是如果数组的一部分已经排序！
如果你觉得这个很混乱，不要让这个表格打扰你太多。 当比较两个算法以确定哪一个更好时，它是最有用的。 但是最终你还是想在实践中测试哪一个真正是最好的。 如果数据量相对较小，即使缓慢的算法在实际运行中也很快。
