文章目录
前言
本文简单介绍了时间复杂度和空间复杂度。
一、时间复杂度（Time Complexity）
定义
定义：描述算法运行时间随输入数据规模（通常用
𝑛 表示）增长的变化趋势，用大 𝑂符号表示（如 𝑂(𝑛)）。它关注的是时间增长的渐进趋势，而非具体执行时间。
1. 常见时间复杂度类型
复杂度 名称 典型场景
𝑂(1)常数时间 直接访问数组元素、哈希表插入/查询（理想情况）
𝑂(log𝑛)对数时间 二分查找、平衡二叉搜索树操作
𝑂(𝑛)线性时间 遍历数组、链表操作
𝑂(𝑛log𝑛)
线性对数时间 快速排序、归并排序𝑂(𝑛2)平方时间 冒泡排序、选择排序（双重循环）
𝑂(2𝑛)指数时间 穷举所有子集（如暴力递归解决旅行商问题）
𝑂(𝑛!)阶乘时间 全排列问题
2. 计算规则
忽略常数项
𝑂(2𝑛)→𝑂(𝑛)
保留最高阶项
𝑂(𝑛2+𝑛)→𝑂(𝑛2)
循环嵌套
循环层数决定幂次（如双重循环为 𝑂(𝑛2)）
递归算法
递归调用次数与递归树深度相关（如斐波那契递归为 𝑂(2𝑛)）
3. 代码示例
（1）𝑂(1)：常数时间
def get_first_element(arr):
return arr[0] # 直接访问数组第一个元素，时间与数组大小无关
（2）𝑂(𝑛)：线性时间
def sum_array(arr):
total = 0
for num in arr: # 遍历数组，执行次数与数组长度n成正比
total += num
return total
（3）𝑂(𝑛2)：平方时间python
def bubble_sort(arr):
n = len(arr)
for i in range(n): # 外层循环n次
for j in range(n-i-1): # 内层循环n-i-1次
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# 总操作次数 ≈ n*(n-1)/2 → O(n^2)
（4）𝑂(log𝑛)：对数时间
def binary_search(arr, target):
left, right = 0, len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # 每次搜索范围缩小一半
else:
right = mid - 1
return -1
二、空间复杂度（Space Complexity）
定义
定义：描述算法运行过程中临时占用的内存空间随输入数据规模 𝑛增长的最大趋势，同样用大 𝑂表示。包括：
指令空间（代码本身）、数据空间（变量、动态分配的内存）、栈空间（递归调用时的上下文存储）
1. 常见空间复杂度类型
复杂度 名称 典型场景
𝑂(1)常数空间 原地排序（如冒泡排序）、单变量计算
𝑂(𝑛)线性空间 存储长度为n的数组、哈希表
𝑂(𝑛2)平方空间 二维数组（如邻接矩阵）
𝑂(log𝑛)对数空间 递归树深度为对数（如快速排序的递归栈）
2. 代码示例
（1）𝑂(1)：常数空间
def reverse_string(s):
# 原地修改列表，不额外分配内存
left, right = 0, len(s)-1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
（2）𝑂(𝑛)：线性空间
def copy_array(arr):
new_arr = [] # 新数组占用空间与输入数组大小n成正比
for num in arr:
new_arr.append(num)
return new_arr
（3）𝑂(𝑛)的递归调用（栈空间）
def factorial(n):
if n <= 1:
return 1
return n * factorial(n-1) # 递归深度为n，栈空间占用O(n)
（4）𝑂(log𝑛)的递归调用
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid+1, right) # 递归深度为log₂n
else:
return binary_search_recursive(arr, target, left, mid-1)
三、对比与注意事项
维度 时间复杂度 空间复杂度
关注点 算法执行时间增长趋势 算法内存占用增长趋势
优化方向 减少循环次数、选择高效算法 减少变量数量、复用内存
常见取舍 时间换空间（如缓存） 空间换时间（如哈希表）
四、实际应用场景
时间敏感型场景
时间敏感型场景（如高频交易系统）：优先优化时间复杂度。
内存受限创景
内存受限场景（如嵌入式设备）：优先优化空间复杂度。
递归算法
递归算法：需同时考虑递归调用栈的空间复杂度（如深度优先搜索可能引发栈溢出）。
五、总结
时间复杂度回答“算法跑多快”，空间复杂度回答“算法占多大内存”。
实际编码中需根据需求权衡两者，例如：
快速排序：时间 𝑂(𝑛log𝑛)，空间 𝑂(log𝑛)（递归栈）。
归并排序：时间 𝑂(𝑛log𝑛)，空间𝑂(𝑛)（额外数组）。
大O表示法是理论分析工具，实际性能还需结合常数因子和硬件特性。