计算时间复杂度

· · 个人记录

基本概念

时间复杂度通常用大 O 符号来表示，它描述了算法运行时间随输入规模增长的渐近上界。例如，O(n) 表示算法的运行时间与输入规模 n 成正比，O(n^2) 表示运行时间与 n 的平方成正比。

计算步骤

1. 确定输入规模

首先要明确代码中输入规模的度量，通常用一个变量（如 n、m 等）来表示。例如，在一个处理数组的算法中，输入规模可能是数组的长度；在一个处理图的算法中，输入规模可能是图的顶点数或边数。

2. 分析基本操作

找出代码中执行的基本操作，这些操作通常是常数时间内完成的，如赋值、比较、算术运算等。基本操作的执行时间可以看作是一个固定的常数，记为 O(1)。

3. 计算基本操作的执行次数

根据代码的结构和逻辑，分析每个基本操作在不同输入规模下的执行次数。这通常需要考虑循环、递归等控制结构对基本操作执行次数的影响。

4. 确定时间复杂度

根据基本操作的执行次数，找出其与输入规模之间的关系，并用大 O 符号表示。常见的时间复杂度有：

常见代码结构的时间复杂度分析

1. 顺序结构

顺序结构中的代码按顺序依次执行，每个基本操作的执行次数是固定的，因此顺序结构的时间复杂度为 O(1)。

# 顺序结构示例
a = 1
b = 2
c = a + b

2. 循环结构

循环结构的时间复杂度取决于循环的嵌套层数和每次循环中基本操作的执行次数。

单层循环
# 单层循环示例
n = 10
for i in range(n):
    print(i)

在这个例子中，循环体中的基本操作（print(i)）执行了 n 次，因此时间复杂度为 O(n)。

多层嵌套循环
# 多层嵌套循环示例
n = 10
for i in range(n):
    for j in range(n):
        print(i, j)

在这个例子中，外层循环执行 n 次，内层循环对于外层循环的每次执行都执行 n 次，因此基本操作（print(i, j)）的执行次数为 n \times n = n^2，时间复杂度为 O(n^2)。

3. 递归结构

递归结构的时间复杂度通常需要通过递归方程来求解。常见的方法有代入法、递归树法和主定理法。

递归示例
# 递归示例：计算阶乘
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

在这个例子中，递归函数 factorial 每次调用自身时，输入规模 n 减 1，直到 n 为 0 或 1 时停止。因此，递归的深度为 n，每次递归调用中基本操作的执行次数为常数，所以时间复杂度为 O(n)。

综合示例

# 综合示例
n = 10
m = 20
# 顺序结构
a = 1
b = 2
# 单层循环
for i in range(n):
    print(i)
# 多层嵌套循环
for i in range(n):
    for j in range(m):
        print(i, j)

在这个例子中，顺序结构的时间复杂度为 O(1)，单层循环的时间复杂度为 O(n)，多层嵌套循环的时间复杂度为 O(nm)。由于 O(nm) 是增长最快的项，因此整个代码的时间复杂度为 O(nm)。

通过以上步骤和方法，我们可以计算出代码的时间复杂度，从而评估算法的效率。在实际应用中，我们通常希望选择时间复杂度较低的算法，以提高程序的运行效率。