算法复杂度分析

在算法设计中，首先要找到问题的解法，然后寻求既快又省的最优解法

• 快，时间效率，算法运行的快慢
• 省，空间效率：算法占用内存空间的大小

动态分析法：实际测试

测试结果受数据规模影响较大，且依赖测试环境，比如同一算法在不同的硬件配置下可能性能不一致。

• time

import time

start_time = time.time()  # 开始时间
pass  # 待测算法
end_time = time.time()  # 结束时间

print(end_time - start_time)  # 耗时

• timeit

timeit.timeit(stmt, setup, timer, number)
"""
stmt: 语句，statement的缩写，要测试的代码或者语句，默认值是"pass"
setup: 在运行stmt前的配置语句，默认值"pass"
timer: 计时器，一般忽略这个参数
number: 语句的执行次数，默认100万次
"""
# 由于stmt只能是语句，需要借助匿名函数来测试函数
t = timeit.timeit(lambda:range(10), number=500)
print(t)

静态分析法：理论估算

渐近复杂度分析（Asymptotic Complexity Analysis），描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势，关注的不是运行时间或占用空间的具体值，而是时间或空间增长的快慢，反映了算法运行效率与输入数据体量之间的关系。

• 时间复杂度（Time Complexity）
• 空间复杂度（Space Complexity）

时间复杂度分析本质上是计算操作数量的渐近上界（asymptotic upper bound）

设算法的操作数量是一个跟输入数据规模 \(n\) 相关的函数，记为 \(T(n)\)

• 数据规模：\(n\)
• 代码总执行次数：\(f(n)\)
• 每行代码执行时间：\(t\)
• 代码总执行时间：\(T(n) = f(n) * t\)

在不运行代码的情况下，假设 \(t\) 相同，\(n\) 趋向无穷，则常量系数、低阶、底阶等对增长趋势的影响都可以忽略，即：T(n) = O(f(n))

大 \(O\) 记号（big-notation）\(O(n)\) 称作 \(T(n)\) 的渐进上界，也叫大 \(O\) 复杂度

准确来讲，函数渐近上界对应的是最差时间复杂度，用符号 \(O(n)\) 表示，渐近下界对应最佳时间复杂度，用 \(\Omega(n)\) 表示，平均时间复杂度用 \(\Theta(n)\) 表示

最差和最佳通常只出现在特殊的数据分布中，而平均复杂度虽然比较真实，但需要假设输入是均匀分布的，计算比较复杂，所以虽然平均时间复杂度更有意义，但关注和实际计算的其实是最差复杂度。

空间复杂度的推算方法与时间复杂度大致相同，统计对象变成了使用空间大小，而且我们通常只关注最差空间复杂度，因为需要确保所有输入数据都有足够的内存空间预留。

在实际情况中，同时优化时间复杂度和空间复杂度是矛盾且困难的，大多数情况下，都需要以空间换时间。

分析方法

• 找循环次数最多的代码段

def test():
  sum = 0  # t
  i = 1  # t
  while i <= n:  # nt
    sum = sum + i  # nt
    i = i + 1  # nt

  return sum

# T(n) = (2+3n)t
# 时间复杂度：O(n)

• 找嵌套最多，量级最大的那一段代码

def test():
  sum = 0  # t
  i = 1  # t
  while i <= n:  # nt
    j = 1  # nt
    while j <= n:  # n^2t
      sum = sum + i * j  # n^2t
      j = j + 1  # n^2t

  return sum

# T(n) = (2+2n+3n^2)t
# 时间复杂度：O(n^2)

• 若最大有多段则相加，有嵌套则相乘

def f1(n):
  ret = 0
  i = 1
  while i < n:
    ret = ret + f2(i)  # 这里调用了另一个函数f2
    n = n + 1

def f2(n):
  sum = 0
  i = 1
  while i < n:
    sum = sum + i
  return sum

# T(n) = T1(n) * T2(n)
# 时间复杂度为：O(n^2)

时间复杂度

\(O(1)\) < \(O(logn)\) < \(O(n)\) < \(O(nlogn)\) < \(O(n^2)\) < \(O(2^n)\) < \(O(n^!)\)

常数阶

只要算法中不存在循环或递归语句，无论有多少行代码，都属于常数阶，即使有循环，但循环次数与输入数据大小无关，也属于常数级

def constant(n: int) -> int:
    count = 0
    for _ in range(100000):
        count += 1
    return count

# 循环次数与传入参数n无关，复杂度：O(1)

线性阶

通常出现在单层循环中，循环次数与输入大小呈线性关系

def linear(n: int) -> int:
    count = 0
    for _ in range(n):
        count += 1
    return count

平方阶

通常出现在嵌套循环中，比如冒泡排序

def bubble_sort(nums: list[int]) -> int:
    count = 0  # 计数器
    # 外循环：未排序区间为 [0, i]
    for i in range(len(nums) - 1, 0, -1):
        # 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # 交换 nums[j] 与 nums[j + 1]
                tmp: int = nums[j]
                nums[j] = nums[j + 1]
                nums[j + 1] = tmp
                count += 3  # 元素交换包含 3 个单元操作
    return count

"""
外循环：n - 1
内循环：n/2
相乘后复杂度为：O(n^2)
"""

指数阶

常见于递归函数、穷举法（暴力搜索、回溯等），指数阶增长非常迅速，对于数据规模较大的问题是不可接受的，通常需要使用动态规划或贪心算法等来解决

# 细胞分裂
def exponential(n: int) -> int:
    count = 0
    base = 1
    # 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
    for _ in range(n):
        for _ in range(base):
            count += 1
        base *= 2
    return count

# count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1

对数阶

与指数阶相反，对数阶反映了每轮缩减到一半的情况

对数阶常出现于基于分治策略的算法中，体现了一分为多和化繁为简的算法思想。它增长缓慢，是仅次于常数阶的理想的时间复杂度。

def logarithmic(n: float) -> int:
    count = 0
    while n > 1:
        n = n / 2
        count += 1
    return count

线性对数阶

快速排序、归并排序、堆排序等主流排序算法的时间复杂度通常都为 \(O(nlogn)\)

def linear_log_recur(n: float) -> int:
    if n <= 1:
        return 1
    count: int = linear_log_recur(n // 2) + linear_log_recur(n // 2)
    for _ in range(n):
        count += 1
    return count

阶乘阶

\(O(n^!)\)

def factorial_recur(n: int) -> int:
    """阶乘阶（递归实现）"""
    if n == 0:
        return 1
    count = 0
    # 从 1 个分裂出 n 个
    for _ in range(n):
        count += factorial_recur(n - 1)
    return count

最好最坏时间复杂度

# 在一个长度不固定的无序列表中，查找元素x所在的位置
# 找到则停止查找，遍历完后没找到则返回-1
def find(_list, x):
  pos = -1
  for i in len(_list):
    if _list[i] == x:
      pos = i
      break
  return pos

在示例中，要查找的元素x，可能会出现在列表的任意位置，亦或者不在列表中，共有 \(n+1\) 种情况，于是复杂度需要根据不同情况进行分析：

• 如果 \(x\) 位于首位,则时间复杂度为 \(\Omega(1)\)，称之：最佳时间复杂度
• 如果 \(x\) 位于末位，则时间复杂度为 \(O(n)\)，称之：最差时间复杂度
• 但大多数情况下元素都不位于首位或末位，于是我们需要引出：平均时间复杂度

假设元素x在列表中和不在列表中的概率各自为 \(1/2\)，如果在列表中，则每个位置的概率相等，均为 \(1/2 * 1/n\)，即 \(1/2n\)

总遍历次数，即加权平均值为：\((1+2+3+...+n)/2n + n*1/2\)，前 n 项和为：\(n(1+n)/2\)，最后：\(T(n)=(3n+1)/4\)，忽略系数等，最终的平均时间复杂度为：\(\Theta(n)\)

均摊时间复杂度

# 向一个长度为n的列表中插入新数据value，如果列表有剩余空间，则直接插入
# 如果列表没有剩余空间，则先计算其元素总和sum，然后清空列表后将sum插入到列表的首位，再继续插入value
_list = [1,2,3...n]
count = 0
def insert(value):
  if count == len(_list):
    sum = 0
    for i in len(_list):
      sum = sum + _list[i]

    _list.insert(0, sum)
    count = 1

  _list.insert(count, value)
  count = count + 1

在示例中，根据不同情况分析：

• 理想的情况下，列表有剩余空间，直接插入即可，即最佳时间复杂度为 \(\Omega(1)\)
• 最差的情况下，没有剩余空间，需要遍历一次列表求和，所以最差时间复杂度为 \(O(n)\)
• 平均情况呢？

对于该示例来说，列表要么有剩余，要么没有剩余，只有这两种情况，而且有剩余空间的概率远大于没有剩余空间的情况，我们没必要再计算其加权平均值，也就是说绝大多数情况都属于理想的情况，复杂度都是 \(\Theta(1)\)，称之为均摊时间复杂度，算是平均情况时间复杂度的一种特殊情况。

空间复杂度

算法运行过程中使用的内存空间主要包括

• 输入空间：存储算法的输入数据
• 暂存空间
  • 暂存数据：保存算法运行过程中的各种常量、变量、对象等
  • 栈桢空间：保存调用函数的上下文数据
  • 指令空间：保存编译后的程序指令
• 输出空间：存储算法的输出数据

class Node:
    """类"""
    def __init__(self, x: int):
        self.val: int = x              # 节点值
        self.next: Node | None = None  # 指向下一节点的引用

def function() -> int:
    """函数"""
    # 执行某些操作...
    return 0

def algorithm(n) -> int:  # 输入数据
    A = 0                 # 暂存数据（常量，一般用大写字母表示）
    b = 0                 # 暂存数据（变量）
    node = Node(0)        # 暂存数据（对象）
    c = function()        # 栈帧空间（调用函数）
    return A + b + c      # 输出数据

空间复杂度通常只统计暂存数据、栈帧空间和输出数据三部分

常数阶

常数阶常见于数量与输入数据大小 \(n\) 无关的常量、变量、对象

在循环中初始化变量或调用函数而占用的内存，在进入下一循环后栈桢空间就会被释放，因此不会累积占用空间，，所以虽然循环了 \(n\) 次，时间复杂度为 \(O(n)\)，但空间复杂度仍为 \(O(1)\)

def function() -> int:
    return 0

def constant(n: int):
    # 常量、变量、对象占用 O(1) 空间
    a = 0
    nums = [0] * 10000
    node = ListNode(0)

    # 循环中的变量占用 O(1) 空间
    for _ in range(n):
        c = 0

    # 循环中的函数占用 O(1) 空间
    for _ in range(n):
        function()

线性阶

线性阶常见于元素数量与 \(n\) 成正比的数组、链表、栈、队列等

def linear(n: int):
    # 长度为 n 的列表占用 O(n) 空间
    nums = [0] * n

    # 长度为 n 的哈希表占用 O(n) 空间
    hmap = dict[int, str]()
    for i in range(n):
        hmap[i] = str(i)

def linear_recur(n: int):
    print("递归 n =", n)
    if n == 1:
        return
    # 时间和空间复杂度都为 O(n)
    linear_recur(n - 1)

平方阶

平方阶常见于矩阵和图，元素数量与 \(n\) 成平方关系

def quadratic(n: int):
    # 二维列表占用 O(n^2) 空间
    num_matrix = [[0] * n for _ in range(n)]

指数阶

指数阶常见于二叉树

def build_tree(n: int) -> TreeNode | None:
    """指数阶（建立满二叉树）"""
    if n == 0:
        return None
    root = TreeNode(0)
    root.left = build_tree(n - 1)
    root.right = build_tree(n - 1)
    return root

对数阶

对数阶常见于分治算法，例如归并排序。