算法入门-时间复杂度与空间复杂度

算法复杂度是衡量算法性能的一个重要指标，它描述了算法执行所需时间和资源（通常是计算步骤数或内存使用量）与输入数据规模的关系。算法复杂度通常用大O符号（Big O notation）来表示，最常见的是时间复杂度和空间复杂度。

时间复杂度

算法的时间复杂度是指算法在执行时所需的时间与输入数据规模之间的关系。它是衡量算法效率的一个重要标准。

常见的时间复杂度类别

常数时间复杂度 - O(1)：算法的执行时间与输入数据的规模无关。

1
2
3

# 示例代码 访问数组的特定索引
def access_element(arr, index):
    return arr[index]

线性时间复杂度 - O(n)：算法的执行时间与输入数据的规模成正比。

# 示例代码 遍历数组
def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

平方时间复杂度 - O(n^2)：算法的执行时间与输入数据规模的平方成正比。

# 示例代码 双层循环
def sum_of_pairs(arr):
    total = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            total += arr[j]
    return total

对数时间复杂度 - 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(n log n)：常见于排序算法，如快速排序和归并排序。

# 示例代码 快速排序
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

指数时间复杂度 - O(2^n)：算法的执行时间与输入数据规模的指数成正比。

# 示例代码 暴力搜索
def brute_force_search(options, target):
    for option in options:
        if option == target:
            return True
    return False

时间复杂度通常关注最坏情况下的性能，但也有时会考虑平均情况或最佳情况的时间复杂度。

空间复杂度

算法的空间复杂度是指算法在执行过程中所需的存储空间量与输入数据规模之间的关系。它是用来衡量算法在内存使用效率上的一个重要指标。

常见的空间复杂度类别

O(1) - 常数空间复杂度：算法所需的存储空间不随输入规模的变化而变化。

# 示例：使用一个固定大小的变量来存储结果。
def max_value_in_list(lst):
    max_val = lst[0]
    for num in lst:
        if num > max_val:
            max_val = num
    return max_val

O(n) - 线性空间复杂度：算法所需的存储空间与输入数据的规模成正比。

1
2
3

# 示例：创建一个与输入列表同样大小的新列表。
def create_copy(lst):
    return [x for x in lst]

**O(n^2) - 平方空间复杂度:**算法所需的存储空间与输入数据规模的平方成正比。

1
2
3

# 示例：创建一个二维列表，其行数和列数都与输入数据规模有关。
def create_matrix(n):
    return [[0 for _ in range(n)] for _ in range(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 True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

**O(k) - 多项式空间复杂度:**算法所需的存储空间与输入数据规模的多项式成正比，其中k是多项式的度数。

1
2
3

# 示例：创建一个大小为n^k的列表，其中k是一个常数。
def create_high_degree_space(n, k):
    return [[0 for _ in range(n)] for _ in range(n**k)]

**O(2^n) - 指数空间复杂度:**算法所需的存储空间与输入数据规模的指数成正比。

# 示例：使用递归创建所有可能的二进制字符串。
def all_binary_strings(n):
    if n == 0:
        return ['']
    return all_binary_strings(n-1) + ['0' + s for s in all_binary_strings(n-1)] + ['1' + s for s in all_binary_strings(n-1)]

在分析空间复杂度时，通常只考虑额外使用的存储空间，而不包括输入数据本身占用的空间。此外，空间复杂度的分析也关注最坏情况下的空间使用，但在某些情况下，平均情况或最佳情况的空间复杂度也是值得考虑的。

在实际应用中，算法的选择往往需要在时间复杂度和空间复杂度之间做出权衡。