algorithm - n 选择 2 的复杂度在 Theta (n^2) 中？

Question

我正在阅读算法简介第 3 版（Cormen 和 Rivest），在第 69 页的“强力解决方案”中，他们指出 n 选择 2 = Theta (n^2)。我认为它会在 Theta (n!) 中。为什么 n 选择 2 紧密绑定到 n 平方？谢谢！

Answer 1

n 选择 2 是

n(n - 1) / 2

这是

n ² / 2 - n/2

我们可以看到 n(n-1)/2 = Θ(n ² ) 通过在 n 趋于无穷时取它们的比率的极限：

lim _{n → ∞} (n ² / 2 - n / 2) / n ² = 1/2

由于这是一个有限的非零量，因此我们有 n(n-1)/2 = Θ(n ² )。

更一般地说：n 为任何固定常数 k 选择 k 是 Θ(n ^k )，因为它等于

嗯！/ (k!(n - k)!) = n(n-1)(n-2)...(n-k+1) / k!

这是 n 中具有非零前导系数的 k 次多项式。

希望这可以帮助！