math.comb 时间复杂度详解

为什么 math.comb 的时间复杂度是 O(k)？

1. 基本事实

Python 的 math.comb(n, k) 函数的时间复杂度是 O(k)，而不是 O(n)。

2. 实现原理

math.comb 使用高效的迭代算法，避免计算大阶乘，而是直接通过公式计算：

C(n, k) = n × (n-1) × (n-2) × ... × (n-k+1) / (k × (k-1) × ... × 1)

3. 算法流程

伪代码实现：

def comb(n, k):
    if k > n - k:
        k = n - k  # 利用对称性 C(n,k) = C(n,n-k)，选择较小的 k
    
    result = 1
    for i in range(k):
        result = result * (n - i) // (i + 1)
    
    return result

4. 时间复杂度分析

• 循环次数：循环执行 k 次（或 min(k, n-k) 次，利用对称性优化）
• 每次循环：
  • 乘法：O(1)（对于小整数）
  • 除法：O(1)（对于小整数）
• 总时间复杂度：O(k)

5. 为什么不是 O(n)？

如果使用阶乘公式 C(n, k) = n! / (k! × (n-k)!)：

• 需要计算 n!，需要 O(n) 次乘法
• 需要计算 k!，需要 O(k) 次乘法
• 需要计算 (n-k)!，需要 O(n-k) 次乘法
• 总时间复杂度：O(n) + O(k) + O(n-k) = O(n)

但 math.comb 的实现避免了计算完整的阶乘，只计算必要的项，因此时间复杂度降为 O(k)。

6. 对于 math.comb(2*n, n) 的情况

math.comb(2*n, n)  # 计算 C(2n, n)

• k = n
• 时间复杂度：O(n)
• 循环执行 n 次，每次计算一个项

7. 空间复杂度

• 只使用常数个变量（result, i 等）
• 空间复杂度：O(1)

8. 优势

1. 避免大数运算：不需要计算 (2n)! 这样的大数
2. 减少溢出风险：通过交替乘除，中间结果更小
3. 提高效率：只计算必要的项，而不是完整的阶乘

9. 示例

计算 C(10, 5)：

传统方法：
C(10, 5) = 10! / (5! × 5!) = 3628800 / (120 × 120) = 252
需要计算：10! (10次乘法) + 5! (5次乘法) + 5! (5次乘法) = 20次运算

math.comb 方法：
C(10, 5) = (10 × 9 × 8 × 7 × 6) / (5 × 4 × 3 × 2 × 1) = 252
只需要：5次乘法和5次除法 = 10次运算

10. 总结

• math.comb(n, k) 的时间复杂度是 O(k)，不是 O(n)
• 对于 math.comb(2*n, n)，k = n，所以时间复杂度是 O(n)
• 实现通过避免计算大阶乘来提高效率
• 空间复杂度是 O(1)