n选择2的复杂度在Theta（n ^ 2）中？

我正在阅读《算法导论》第三版（Cormen和Rivest），在“暴力解决方案”的第69页上，他们指出n选择2 = Theta（n ^

2）。我认为它应该在Theta（n！）中。为什么n选择2紧密绑定到n平方？谢谢！

n选择2是

n（n-1）/ 2

这是

n 2 /2-n / 2

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

lim n→∞（n 2 /2-n / 2）/ n 2 = 1/2

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

更笼统地说：对于任何固定常数，n选择k为Θ（n k），因为它等于

n！/（k！（n-k）！）= n（n-1）（n-2）…（n-k + 1）/ k！

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

希望这可以帮助！