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

我在阅读Introduction to Algorithms 3rd Edition (Cormen and Rivest)，并在第69页上的“蛮力解决方案”中声明n选择2 = Theta（n^2）。相反，我认为它会在Theta（n！）中。为什么n选择2紧紧地n平方？谢谢！n选择2的复杂性在Theta（n^2）中？

n选择2 = n（n + 1）/ 2 =（n^2 + n）/ 2 ... –

Cormen是对的。 – 0x90

@ DennisMeng-它是n（n-1）/ 2而不是n（n + 1）/ 2。 – templatetypedef

Ñ选择2是

N（N - 1）/ 2

这是

Ñ/2 + n/2个

我们可以看到n（n-1）/ 2 = Θ（N ）通过取它们的比率的限制随着n趋于无穷：

LIM _{Ñ→ ∞}（N /2 + N/2）/ N = 1/2

由于这出来到一个有限的，非零数量，我们有N（N-1）/ 2 = Θ（N ）。

更普遍：N选择k对于固定常数k Θ（N ^ķ），因为它是等于

N！ /（k！（n-k）！）= n（n-1）（n-2）...（n-k + 1）/ k！

这是一个非零前导系数的n阶k次多项式。

希望这会有所帮助！

2013-10-17 00:05:59 templatetypedef

当然！我出于某种原因认为选择k是（n！）/（k！）。 –

@ JennyShoars-这肯定会让人困惑。希望这清除了事情！ – templatetypedef

回答