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

Question

我正在阅读 Introduction to Algorithms 3rd Edition (Cormen and Rivest)在第 69 页的“A brute-force solution”中，他们声明 n 选择 2 = Theta (n^2)。我认为它会在 Theta (n!) 中。为什么 n choose 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 choose k for any fixed constant k is Θ(n^k), 因为它等于

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

它是 n 中首项系数非零的 k 次多项式。

希望这对您有所帮助!