n选择2的复杂度在Theta(n ^ 2)中? [英] The complexity of n choose 2 is in Theta (n^2)?
问题描述
我正在阅读算法简介第3版(Cormen和Rivest) 并在暴力解决方案"的第69页上指出,n选择2 = Theta(n ^ 2).我认为它应该在Theta(n!)中.为什么n选择2紧密绑定到n平方?谢谢!
I'm reading Introduction to Algorithms 3rd Edition (Cormen and Rivest) and on page 69 in the "A brute-force solution" they state that n choose 2 = Theta (n^2). I would think it would be in Theta (n!) instead. Why is n choose 2 tightly bound to n squared? Thanks!
推荐答案
n选择2是
n(n-1)/2
n(n - 1) / 2
这是
n 2 /2-n/2
当n变为无穷大时,通过取其比率的限制,我们可以看到n(n-1)/2 =Θ(n 2 ):
We can see that n(n-1)/2 = Θ(n2) by taking the limit of their ratios as n goes to infinity:
lim n→ ∞ (n 2 /2-n/2)/n 2 = 1/2
limn → ∞ (n2 / 2 - n / 2) / n2 = 1/2
由于这是一个有限的非零量,所以我们有n(n-1)/2 =Θ(n 2 ).
Since this comes out to a finite, nonzero quantity, we have n(n-1)/2 = Θ(n2).
更一般而言:n为任意固定常数选择k k为Θ(n k ),因为它等于
More generally: n choose k for any fixed constant k is Θ(nk), because it's equal to
n! /(k!(n-k)!)= n(n-1)(n-2)...(n-k + 1)/k!
n! / (k!(n - k)!) = n(n-1)(n-2)...(n-k+1) / k!
这是n中的第k次多项式,且前导系数非零.
Which is a kth-degree polynomial in n with a nonzero leading coefficient.
希望这会有所帮助!
这篇关于n选择2的复杂度在Theta(n ^ 2)中?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!