关系型数据库是怎么工作的2:时间复杂度

作者:51ak

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

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

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

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

先说一些看法:

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

时间复杂度有多种类型:

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

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

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

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

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

发布日期:2017/09/10

Categories: 数据库理论 翻译 关系型数据库 mysql Tags: 转译 精品