复杂度计算

评论
14 views

复杂度计算是算法分析中的一个重要概念，用于评估算法在不同输入规模下的时间或空间需求。以下是常见的复杂度类型及其计算方法：

1. 时间复杂度

时间复杂度衡量算法运行时间随输入规模增长的变化趋势。

常见时间复杂度

  • O(1): 常数时间，操作时间与输入规模无关。
  • O(log n): 对数时间，常见于二分查找等算法。
  • O(n): 线性时间，操作时间与输入规模成正比。
  • O(n log n): 线性对数时间，常见于快速排序、归并排序等。
  • O(n²): 平方时间，常见于简单排序算法如冒泡排序。
  • O(n³): 立方时间，常见于三重循环算法。
  • O(2ⁿ): 指数时间，常见于递归算法如汉诺塔问题。
  • O(n!): 阶乘时间，常见于排列组合问题。

计算方法

  • 基本操作计数: 计算算法中基本操作的执行次数。
  • 忽略低阶项和常数: 只保留最高阶项并忽略常数系数。

示例:

for i in range(n):
    for j in range(n):
        print(i, j)

时间复杂度为 O(n²)，因为有两层循环，每层循环次数为 n。

2. 空间复杂度

空间复杂度衡量算法所需内存空间随输入规模增长的变化趋势。

常见空间复杂度

  • O(1): 常数空间，所需空间与输入规模无关。
  • O(n): 线性空间，所需空间与输入规模成正比。
  • O(n²): 平方空间，常见于二维数组。

计算方法

  • 变量和数据结构: 计算算法中变量和数据结构占用的空间。
  • 忽略低阶项和常数: 只保留最高阶项并忽略常数系数。

示例:

def create_matrix(n):
    return [[0] * n for _ in range(n)]

空间复杂度为 O(n²)，因为创建了一个 n×n 的二维数组。

3. 复杂度分析示例

示例 1: 线性搜索

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
  • 时间复杂度: O(n)，最坏情况下需要遍历整个数组。
  • 空间复杂度: O(1)，只使用了常数个额外空间。

示例 2: 归并排序

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)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
  • 时间复杂度: O(n log n)，每次递归将数组分成两半，合并操作需要线性时间。
  • 空间复杂度: O(n)，需要额外空间存储合并后的数组。

总结

  • 时间复杂度衡量算法运行时间随输入规模的变化。
  • 空间复杂度衡量算法所需内存空间随输入规模的变化。
  • 复杂度分析通常关注最坏情况，并使用大 O 表示法描述。

通过复杂度分析，可以更好地理解和比较不同算法的性能。