时间复杂度

时间复杂度（Time Complexity）是算法里非常核心的概念，它用来描述：随着输入规模 (n) 增大，算法运行时间增长的趋势。

$f(n)=O(g(n))$

一、为什么需要时间复杂度？

假设我们有两个算法：

• 算法 A：处理 100 个数据花 1 秒
• 算法 B：处理 100 个数据花 2 秒

看起来 A 更快，但如果：

• 数据量变成 100 万

可能：

• A 花 10 小时
• B 花 10 秒

这说明：

真正重要的不是当前运行时间，而是增长趋势。

这就是时间复杂度研究的重点。

二、最常见的表示方式：大 O 表示法（Big-O）

我们通常写：

• $O(1)$
• $O(n)$
• $O(\log n)$
• $O(n^2)$

意思是：

忽略常数、低阶项，只关注"最高阶增长趋势"

例如：

$3n^2 + 5n + 7$

时间复杂度写作：

$O(n^2)$

因为：

• 常数 3 不重要
• $5n$ 是低阶项
• 最主要的是 $n^2$

三、常见时间复杂度（从快到慢）

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

x = arr[0]

不管数据有多少：永远只执行一次。这是最理想的复杂度。

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

典型代表：二分查找（Binary Search）

while left <= right:

每次把问题规模缩小一半。例如：1000 个数 → 最多查 10 次左右。非常高效。

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

for i in arr:

遍历一次数组。数据翻倍，时间也翻倍。

4. O(n log n)

典型代表：

• 快速排序（平均）
• 归并排序
• 堆排序

这是非常优秀的排序复杂度。

5. O(n²) —— 平方级

for i in range(n):
    for j in range(n):

双重循环。典型代表：

• 冒泡排序
• 选择排序
• 插入排序（最坏）

数据稍大就会很慢。

6. O(2^n) —— 指数级

典型代表：

• 暴力递归
• 回溯（未剪枝）

例如：斐波那契暴力递归。非常可怕。

7. O(n!) —— 阶乘级

典型代表：全排列问题。最恐怖的复杂度之一。

四、一个重要误区

很多人会问：

两层 for 循环一定是 $O(n^2)$ 吗？

答案：不一定！

例如：

for i in range(n):
    j *= 2

可能是 $O(n \log n)$。

所以：

不能只看循环层数，要看总执行次数。

这是面试高频点。

五、如何分析时间复杂度（核心方法）

看最坏情况（Worst Case）

因为我们要保证最差情况下系统也能运行。

看循环执行次数

for i in range(n):

就是 O(n)

看递归关系

归并排序：

$T(n)=2T(n/2)+O(n)$

结果：$O(n\log n)$

这个后面我们可以专门讲。

六、记住这张图（非常重要）

$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$

这张图几乎贯穿整个算法学习。