要理解和计算时间复杂度与空间复杂度，关键是分析算法中重复执行的操作次数（时间）和额外开辟的存储空间（空间）如何随输入规模n变化。下面通过具体代码示例详细说明计算方法。
一、时间复杂度计算
时间复杂度关注核心操作的执行次数与n的关系，忽略常数项和低阶项，只保留最高阶项。
示例1：O(1) 常数时间
def get_first_element(arr):return arr[0] # 无论数组长度n多大，只执行1次
- 分析：无论输入规模
n（数组长度）如何变化，操作次数始终为1，因此时间复杂度为 O(1)。
示例2：O(n) 线性时间
def sum_array(arr):total = 0for num in arr: # 循环执行n次（n为数组长度）total += numreturn total
- 分析：循环执行次数与输入规模
n成正比（n次），因此时间复杂度为 O(n)。
示例3：O(n²) 平方时间
def print_pairs(arr):n = len(arr)for i in range(n): # 外层循环n次for j in range(n): # 内层循环n次print(arr[i], arr[j])
- 分析：外层循环
n次，内层循环每次也执行n次，总操作次数为n×n = n²，因此时间复杂度为 O(n²)。
示例4：O(log n) 对数时间
def binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2 # 每次将问题规模缩小一半if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1
- 分析：二分查找每次将搜索范围缩小一半，执行次数为
log₂n（以2为底的对数），因此时间复杂度为 O(log n)。
示例5：O(n log n) 线性对数时间
def merge_sort(arr): # 归并排序if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid]) # 递归拆分（log n层）right = merge_sort(arr[mid:])return merge(left, right) # 合并操作（每层总耗时O(n)）def merge(left, right): # 合并两个有序数组result = []i = j = 0while i < len(left) and j < len(right):if left[i] <= right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return result
- 分析：归并排序通过递归将数组拆分为
log n层，每一层的合并操作总耗时为O(n)，因此总时间复杂度为 O(n log n)。
二、空间复杂度计算
空间复杂度关注算法额外开辟的存储空间与n的关系，不包含输入数据本身的空间。
示例1：O(1) 常数空间
def swap(a, b):temp = a # 只使用1个临时变量，与n无关a = bb = temp
- 分析：无论输入规模如何，额外空间仅为1个临时变量，因此空间复杂度为 O(1)。
示例2：O(n) 线性空间
def copy_array(arr):new_arr = [0] * len(arr) # 新数组长度与n成正比for i in range(len(arr)):new_arr[i] = arr[i]return new_arr
- 分析：创建了一个与输入数组等长的新数组，额外空间为
n，因此空间复杂度为 O(n)。
示例3：O(log n) 对数空间
def factorial_recursive(n): # 递归计算阶乘if n == 0:return 1return n * factorial_recursive(n - 1)
- 分析：递归调用会在栈内存中保存
log n层调用帧（每次递归问题规模减小），因此空间复杂度为 O(log n)。
示例4：O(n²) 平方空间
def create_matrix(n):matrix = []for i in range(n):row = [0] * n # 每行n个元素matrix.append(row)return matrix # 总空间为n×n = n²
- 分析：创建了一个
n×n的二维数组，额外空间为n²，因此空间复杂度为 O(n²)。
三、总结
-
时间复杂度：
统计核心操作的执行次数，保留与n相关的最高阶项（如n² + n简化为O(n²)）。 -
空间复杂度：
统计额外开辟的存储空间（如临时变量、新数组、递归栈等），同样保留最高阶项。 -
常见场景：
- 循环次数与
n成正比 →O(n) - 嵌套循环 →
O(n²)（两层）、O(n³)（三层） - 递归深度为
log n→O(log n) - 新数组长度为
n→O(n)
- 循环次数与
通过这些例子，可以更清晰地理解如何分析算法的效率，从而在实际编程中选择更优的实现方式。