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/2 + n/2

我们可以看到n(n-1)/ 2 =Θ(n ²)乘以它们的比率极限,因为n变为无穷大:

lim _n→∞(n ^2/2 + n/2)/ n ² = 1/2

由于这是有限的非零量,我们有n(n-1)/ 2 =Θ(n ²).

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

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

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

希望这可以帮助!