常见的时间复杂度
计算方法
1、确定输入规模：
输入规模通常用 n 表示，例如数组长度、链表长度等。
2、分析算法的执行步骤：
计算每个操作的执行次数。
确定操作的执行次数与输入规模的关系。
3、忽略常数和低阶项：
在大O表示法中，常数和低阶项可以忽略，只保留最高阶项。
例如，O(3n² + 2n + 1) 简化为 O(n²)。举例：
假设有一个算法，其执行步骤如下：
arr = [1, 2, 3, 4, 5]
for i in arr: # O(n)
for j in arr: # O(n)
print(i, j)
外层循环：执行 n 次。
内层循环：每次外层循环执行 n 次。
总执行次数：n * n = n²。
时间复杂度：O(n²)。
O(1)：常数时间复杂度
不论输入规模如何，算法的执行时间是固定的。
示例：访问数组的某个元素。
arr = [1, 2, 3] print(arr[1]) # 时间复杂度为 O(1)
O(n)：线性时间复杂度
算法的执行时间与输入规模成正比。
示例：遍历一个数组。
arr = [1, 2, 3, 4, 5] for i in arr: print(i) # 时间复杂度为 O(n)
O(n²)：二次时间复杂度
算法的执行时间与输入规模的平方成正比。
示例：嵌套循环。
arr = [1, 2, 3, 4, 5] for i in arr: for j in arr: print(i, j) # 时间复杂度为 O(n²)
O(log n)：对数时间复杂度
算法的执行时间与输入规模的对数成正比。
示例：二分查找。
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 # 时间复杂度为 O(log n)
O(n log n)：线性对数时间复杂度
算法的执行时间与输入规模的对数成正比。
示例：快速排序、归并排序。
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) # 时间复杂度为 O(n log n)
空间复杂度
定义：空间复杂度是指算法在运行过程中消耗的内存资源量级，通常用输入规模（如数组长度、链表长度等）来表示。
表示方法：空间复杂度也用大O符号（O）表示，例如 O(1)、O(n)、O(n²) 等。
计算方法
1）确定输入规模：
输入规模通常用 n 表示，例如数组长度、链表长度等。
2）分析算法使用的额外内存：
计算算法中使用的额外空间（如变量、数组、递归栈等）。
确定额外空间的使用量与输入规模的关系。
3）忽略常数和低阶项：
在大O表示法中，常数和低阶项可以忽略，只保留最高阶项。
例如，O(3n² + 2n + 1) 简化为 O(n²)。
假设有一个算法，其执行步骤如下：
Python复制
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 创建左半部分数组
right = merge_sort(arr[mid:]) # 创建右半部分数组
return merge(left, right) # 合并两个数组递归调用：每次递归调用会创建两个子数组。
空间复杂度：
每次递归调用创建的子数组占用 O(n) 的空间。
递归深度为 O(log n)。
总空间复杂度为 O(n)（递归栈空间）。
常见的空间复杂度
O(1)：常数空间复杂度
不论输入规模如何，算法使用的额外内存是固定的。
示例：交换两个变量的值。
a, b = 1, 2 a, b = b, a # 空间复杂度为 O(1)
O(n)：线性空间复杂度
算法使用的额外内存量与输入规模成正比。
示例：复制一个数组。
arr = [1, 2, 3, 4, 5] new_arr = arr[:] # 空间复杂度为 O(n)
O(n²)：二次空间复杂度
算法使用的额外内存量与输入规模的平方成正比。
示例：创建一个二维数组。
arr = [[0] * n for _ in range(n)] # 空间复杂度为 O(n²)