Home首页 / Lesson 5: Big O第 5 课：复杂度
Lesson 5 · Complexity第 5 课 · 复杂度
What is O(1), O(n), O(log n)?什么是 O(1)、O(n)、O(log n)？
Big O is not about seconds. It is about how the cost grows when the data grows.大 O 说的不是几秒，而是“数据变多时，代价怎么变”。
01The idea先有一个画面
That is O(1), O(n), O(log n). The letter is the data size; the function is how many steps you need.这就是 O(1)、O(n)、O(log n)。字母是数据量，函数是需要的步数。
| Big O大 O | Means意思 | n=1000 steps1000 个时要几步 |
|---|---|---|
| O(1) | one step, no matter how many不管多少，都是一步 | 1 |
| O(log n) | half each time每次砍一半 | about 10约 10 |
| O(n) | one by one一个一个来 | 1000 |
| O(n log n) | sort by halving, n times每次砍一半、做 n 遍 | about 10000约 1 万 |
| O(n²) | every pair两两配对 | 1,000,000100 万 |
02How to read it怎么读出来
“O” is said “big O”. “O(1)” is “big O of one, constant time”. “O(log n)” is “big O of log n”.“O”读作 big O；“O(1)”读 big O of one，也叫常数时间；“O(log n)”读 big O of log n。
We drop the small parts. O(2n + 5) is O(n); O(n² + n) is O(n²). Big O cares about the shape of the curve, not the exact number.小项会被丢掉：O(2n + 5) 就是 O(n)，O(n² + n) 就是 O(n²)。大 O 只看曲线的形状，不看具体数字。
03Where you meet it你会在哪里遇到它
- HashMap get: O(1) on average, O(log n) in a bad bucket, O(n) in the worst case.HashMap 的 get：平均 O(1)，桶里成了树是 O(log n)，最坏 O(n)。
- ArrayList get: O(1). Insert in the middle: O(n).ArrayList 按下标读：O(1)；中间插入：O(n)。
- A double loop over the same list: O(n²) — too slow for big data.对同一个列表写两层循环：O(n²)，数据一大就慢。
In an interview, say the number and why: “O(1), because it computes the bucket from the hash.”面试时说数字，并且说原因：“O(1)，因为它是用 hash 直接算出桶的位置。”
→New words新词
Click ▶ hear it for real people on YouGlish; 🔊 for the computer voice.点 ▶ hear it 听真人发音（YouGlish）；点 🔊 听电脑朗读。
✓Check yourself自测
- In your own words: what is O(n)?用你自己的话说：什么是 O(n)？
- Why is reading an array O(1)?为什么读数组是 O(1)？
- A bucket with 8 items: how many steps at most?桶里有 8 个元素：最多几步？
Answer out loud first. Only then open the answers below.先自己出声答，再看下面的答案。