时间复杂度是用来衡量一个算法执行时间随输入数据规模增长而变化的趋势的指标。它不告诉你具体的秒数，而是告诉你“增长的速度有多快”。
核心思想：关注趋势，而非具体时间
假设你要处理一个包含n个元素的列表：
算法 A 可能需要
n步算法 B 可能需要
n²步
当n很小（比如10）时，差别不大。但当n很大（比如100万）时，n²步会比n步慢无数倍。
时间复杂度就是用来描述这种“增长规律”的数学工具。
大 O 表示法
我们通常用大 O 表示法来描述时间复杂度，比如：
O(1)- 常数时间
O(log n)- 对数时间
O(n)- 线性时间
O(n log n)- 线性对数时间
O(n²)- 平方时间
O(2ⁿ)- 指数时间
直观理解（从最好到最差）：
| 时间复杂度 | 俗称 | n=1000时的感觉 | 例子 |
|---|---|---|---|
| O(1) | 常数时间 | 瞬间完成 | 数组按索引访问 |
| O(log n) | 对数时间 | 几乎瞬间 | 二分查找 |
| O(n) | 线性时间 | 比例增长 | 遍历数组 |
| O(n log n) | 线性对数 | 稍慢但能接受 | 快速排序 |
| O(n²) | 平方时间 | 开始变慢 | 双重嵌套循环 |
| O(2ⁿ) | 指数时间 | 天文数字般慢 | 穷举所有组合 |
具体例子
1. O(1) - 常数时间
def get_first_element(arr): return arr[0] # 无论数组多大，都只做一步2. O(n) - 线性时间
def find_max(arr): max_val = arr[0] for num in arr: # 遍历所有 n 个元素 if num > max_val: max_val = num return max_val # 需要 n 步3. O(n²) - 平方时间
def find_duplicates(arr): duplicates = [] for i in range(len(arr)): # 外层循环 n 次 for j in range(i + 1, len(arr)): # 内层循环平均 n/2 次 if arr[i] == arr[j]: duplicates.append(arr[i]) return duplicates # 总共约 n²/2 步为什么它很重要？
可扩展性预测：帮你预测当数据量增加10倍时，程序会慢多少
算法选择：在设计和面试中选择更高效的算法
问题分类：判断一个问题是否“可高效解决”
实际意义对比：
O(n)算法：数据量×10 → 时间×10
O(n²)算法：数据量×10 → 时间×100
O(2ⁿ)算法：数据量+10 → 时间×1024倍！
计算时的简化原则
计算时间复杂度时，我们忽略常数和低阶项，只保留最高阶项：
3n² + 100n + 500→ 记为O(n²)5n + 20→ 记为O(n)log₂n + 10→ 记为O(log n)
因为当n很大时，n²项占主导地位，其他项的影响微不足道。
总结
时间复杂度就是算法执行时间的“增长速率标尺”：
它告诉你：数据量翻倍时，时间大概会变成几倍
它不告诉你：具体需要多少毫秒
它关注的是：大规模数据下的性能趋势
简单说，它是评估算法“好不好”的一个关键数学指标，能帮助我们在写代码时做出更明智的选择。
