1. O(1) —— 常数时间

通俗描述

数据量增加多少，我做的事情都差不多。

也就是：

10条数据，我处理1步。

10000条数据，我还是处理1步。

速度基本不受数据量影响。

举例

查银行卡余额

你打开手机银行：

输入密码。

看到余额。

不管银行有：

• 100个用户
• 1亿个用户

你查自己的余额，速度差不多。

因为系统根据你的账号直接找到你的数据。

这就是：

O(1)

代码：

const user = userMap[id];

直接根据 id 找用户。

2. O(n) —— 线性时间

通俗描述

数据增加多少，我干活就增加多少。

数据翻10倍。

工作量大概也翻10倍。

举例

找人

一个教室：

10个人。

老师说：

找一下张三。

你一个个看：

第1个人：

不是。

第2个人：

不是。

...

找到张三。

如果教室：

1000个人。

你可能要找：

1000次。

人数越多，查找越慢。

这就是：

O(n)

代码：

for(let item of list){
    if(item.id === id){
        return item;
    }
}

数组越长，循环次数越多。

3. O(log n) —— 对数时间

通俗描述

数据增加很多，但是每次都能排除一大半，所以增长很慢。

这是非常优秀的一种复杂度。

举例：猜数字

我想一个：

1~100之间的数字。

你猜。

普通找：

1、2、3、4...

最多100次。

这是：

O(n)

二分查找：

第一次：

猜50。

我说：

大了。

那么：

51~100全部不用看。

剩一半。

第二次：

猜75。

我说：

小了。

剩：

76~100。

你每次砍掉一半。

大概：

100个数字：

7次左右找到。

100万个数字：

20次左右找到。

这就是：

O(log n)

实际应用：

• 二分查找
• 数据库索引（B树）

4. O(n²) —— 平方时间

多一层循环就多一次平方 三层循环就是O（n3）

通俗描述

数据增加一点，工作量暴涨。

通常出现在：

循环套循环。

举例

一个班有100个人。

要求：

每个人都和其他人握一次手。

那么：

第1个人：

和99个人握手。

第2个人：

和98个人握手。

...

总次数：

接近：

100 × 100

如果：

100个人：

约1万次。

1000个人：

约100万次。

人数增加10倍。

工作增加100倍。

这就是：

O(n²)

代码：

for(let i of list){

    for(let j of list){

    }

}

外层循环一次。

里面再完整循环一次。

放一起比较

假设现在有 10000条数据：

类型通俗理解10000条数据

O(1)直接找到1次

O(log n)每次砍一半约14次

O(n)一个个找10000次

O(n²)两两比较1亿次