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

当n变为无穷大时，通过取其比率的限制，我们可以看到n(n-1)/2 =Θ(n ² ):

We can see that n(n-1)/2 = Θ(n²) by taking the limit of their ratios as n goes to infinity:

lim _{n→ ∞} (n ² /2-n/2)/n ² = 1/2

lim_{n → ∞} (n² / 2 - n / 2) / n² = 1/2

由于这是一个有限的非零量，所以我们有n(n-1)/2 =Θ(n ² ).

Since this comes out to a finite, nonzero quantity, we have n(n-1)/2 = Θ(n²).

更一般而言:n为任意固定常数选择k k为Θ(n ^k )，因为它等于

More generally: n choose k for any fixed constant k is Θ(n^k), 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屋！