如何计算算法时间复杂度

计算算法的时间复杂度，本质上是分析算法执行时间随输入规模增长的变化趋势，通常用**大 O 记号（O 表示法）**来描述。

下面用通俗易懂的方式说明步骤和方法。

一、时间复杂度是什么？

时间复杂度 不表示具体运行秒数，而是表示：

当输入规模 n 变大时，算法执行基本操作次数的增长量级

例如：

• O(1)：常数时间
• O(log n)：对数时间
• O(n)：线性时间
• O(n²)：平方时间

二、基本计算步骤

步骤 1：确定“基本操作”

通常是：

• 赋值
• 比较
• 加减乘除
• 数组访问

步骤 2：找出输入规模 n

常见例子：

• 数组长度
• 矩阵大小
• 图中顶点 / 边数

步骤 3：写出执行次数表达式

统计基本操作执行的次数（用 n 表示）

步骤 4：取最高阶项，忽略常数

只保留增长最快的部分。

三、常见例子

1️⃣ O(1) 常数时间

a = b + c

执行次数与 n 无关 → O(1)

2️⃣ O(n) 线性时间

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

循环执行 n 次 → O(n)

3️⃣ O(n²) 平方时间

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

嵌套循环 → n × n → O(n²)

4️⃣ O(log n) 对数时间

while n > 1:
    n = n // 2

每次规模减半 → O(log n)（典型：二分查找）

5️⃣ O(n log n)

for i in range(n):
    # 内部是 log n 操作

常见于：

• 快速排序（平均）
• 归并排序

四、常见规则总结

五、最坏 / 平均 / 最好复杂度

• 最坏情况（最常用）
• 平均情况
• 最好情况（一般参考）

六、快速判断技巧

• 一层循环 → O(n)
• 两层嵌套 → O(n²)
• 每次减半 → O(log n)
• 分治 + 每层处理 n → O(n log n)

如果你有具体代码或算法（比如排序、查找、递归），我可以直接帮你算时间复杂度。