1 O(1) vs O(n^2)

现如今，很多程序员不关心时间复杂度….好吧，他们是对的！

但当你处理大数据时（我不是说几千个）或者你为了几毫秒的性能在优化，就非常有必要了解这个理论了。刚巧，数据库符合这两种情况！ 不会花费太长时间，只是了解下，这将有助于我们理解后面说的”基于成本的优化”

1.1 时间复杂度概念

时间复杂度被用来表达算法处理已知问题所消耗的时长，为了表达这个复杂度，计算机科学家使用数学上的大O符号。 该符号加上算法需要进行多少次操作函数一起使用。

用下图来说明时间复杂度的差异

O(1) 是静态的 O(log(n)) 保持在一个低复杂度，哪怕有几十亿的数据要处理 O(n^2) 是复杂度最差的

1.2 时间复杂度举例

当数据量少的时候，O(1) 和 O(n^2) 之间的差异是微不足道的。 比如说，当你需要个算法处理2000条数据时

• O(1) 算法花费 1 次操作
• O(log(n)) 算法花费 7 次操作
• O(n) 算法花费 2000 次操作
• O(n*log(n)) 算法花费 14000 次操作
• O(n^2) 算法花费 4000000 次操作

看起来 O(1) 和 O(n^2) 算法好像差了4000000次倍的操作，但最多只多花了2毫秒，跟你眨一次眼睛一样的时间，现代的CPU进程每秒处理几亿次操作，这就是为什么性能和优化在IT项目中显得不那么重要.

正如我说的那样，当处理大量数据时，理解时间复杂度的概念还是非常重要的，这次我们试试处理 1000000条数据（一百万行对数据库来说并不多）

• O(1) 算法花费 1 次操作
• O(log(n)) 算法花费 14 次操作
• O(n) 算法花费 100万 次操作
• O(n*log(n)) 算法花费 140万 次操作
• O(n^2) 算法花费 10000亿 次操作

都不用去计算，这个糟糕的O(n^2) 算法足够你去喝杯咖啡了（甚至再来一杯）！如果再100万条数据后面再加一个0，那就足够你睡一小觉了。

1.3 再深入理解下时间复杂度

先说一些看法：

• 在一个哈希表上 ,搜索一个元素时间复杂度是 O(1)
• 在一个平衡良好的树上 ,搜索一个元素时间复杂度是 O(log(n))
• 在一个数组上 ,搜索一个元素时间复杂度是 O(n)
• 好的排序算法时间复杂度是 O(n*log(n))
• 坏的排序算法时间复杂度是 O(n^2))

Note: 在下一章节中，我们将看到这些数法和数据结构

时间复杂度有多种类型：

• 平均情况
• 最好的情况
• 最坏的情况 时间复杂度通常要考虑的是最坏的情况。

刚才我只谈论时间复杂性(cpu)，但是复杂性也适用于： - 算法的内存消耗 - 算法的磁盘I/O消耗

当然，n^2也不是最差的复杂性，比如说：

• n^4: 真是太烂了，回头我将举一些哪些算法的时间复杂度是这个
• 3^n: 这个还要更烂! 这篇文章一会也会看到这种糟糕的算法应用 (这种可怕的算法竟然真的在数据库中能被使用到).
• factorial n : 哪怕你只有几条数据，你也永远得不到算法的结果
• n^n: 如果你最终用到了这种复杂性，请扪心自问，你是不是真的在做IT…

Note: *这里，我并没有给出这些大O的真实定义，只是给了些基本的想法，你可以在维基百科上得到这些概念的真实定义 *

本节完成，下一章节我们将讨论：合并排序

本篇文章完整分为7节，当前第2节。以下完整章节： 1. 引言 2. 时间复杂度 3. 合并排序 4. 数组.树.哈希表 5. 客户端管理 6. SQL查询 7. 数据管理