当前位置：首页 > news >正文

【时间复杂度和空间复杂度】

news 2025/8/22 2:24:21

常见的时间复杂度

计算方法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) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1  # 时间复杂度为 O(log n)

O(n log n)：线性对数时间复杂度

算法的执行时间与输入规模的对数成正比。

示例：快速排序、归并排序。

def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = 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 arrmid = len(arr) // 2left = 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²)
```