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

常见的时间复杂度

计算方法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²)。

 

1. O(1)：常数时间复杂度

   • 不论输入规模如何，算法的执行时间是固定的。

   • 示例：访问数组的某个元素。

     arr = [1, 2, 3]
     print(arr[1])  # 时间复杂度为 O(1)

2. O(n)：线性时间复杂度

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

   • 示例：遍历一个数组。

     arr = [1, 2, 3, 4, 5]
     for i in arr:print(i)  # 时间复杂度为 O(n)

3. O(n²)：二次时间复杂度

   • 算法的执行时间与输入规模的平方成正比。

   • 示例：嵌套循环。

     arr = [1, 2, 3, 4, 5]
     for i in arr:for j in arr:print(i, j)  # 时间复杂度为 O(n²)

4. 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)

5. 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)（递归栈空间）。

常见的空间复杂度

1. O(1)：常数空间复杂度

   • 不论输入规模如何，算法使用的额外内存是固定的。

   • 示例：交换两个变量的值。

     a, b = 1, 2
     a, b = b, a  # 空间复杂度为 O(1)

2. O(n)：线性空间复杂度

   • 算法使用的额外内存量与输入规模成正比。

   • 示例：复制一个数组。

     arr = [1, 2, 3, 4, 5]
     new_arr = arr[:]  # 空间复杂度为 O(n)

3. O(n²)：二次空间复杂度

   • 算法使用的额外内存量与输入规模的平方成正比。

   • 示例：创建一个二维数组。

     arr = [[0] * n for _ in range(n)]  # 空间复杂度为 O(n²)