algorithm - 组合的渐近运行时间是多少？

Question

我有递归关系 T(n, k) = T(n - 1, k - 1) + T(n - 2, k - 1) + ... + T(k + 1, k - 1 ).这是 T(n - i, k - 1) 从 i = 1 到 i = n - k + 1 的总和。手工计算结果，我注意到这形成了帕斯卡三角形 - T(n, k)然后是 (n - 1) 选择 (k - 1)。

我如何用大 O 表示法将其表示为渐近运行时间？我可以证明 T(n, k) 是 O(n!)，但这并不能真正展示全貌——如果 n 很大，但 k 也一样大怎么办？如果 n = k，则运行时间仅为 1。

Answer 1

如果您将帕斯卡三角形视为一个矩阵，并且您想要找出构建该矩阵的复杂性，其大小为 n x k，那么它的大哦将是 O( n*k)。显然，没有比这更好的了，因为那是矩阵的大小。

我们如何得到它？对组合使用以下简化的循环:

C(n, k) = C(n - 1, k) + C(n - 1, k - 1)

仅计算一个组合具有相同的复杂性(如果使用内存)。