n个元素中选取2个元素的复杂度在Theta(n^2)吗？

Question

我正在阅读 算法导论第三版（Cormen和Rivest），在第69页的“暴力解法”中，他们指出n个选择2个= Theta (n ^ 2)。 我认为它应该是Theta (n！)。 为什么n个选择2个与n平方紧密绑定？谢谢！

- Jenny Shoars

---

n选2 = n(n+1)/2 = (n^2 + n)/2... - Dennis Meng

@DennisMeng- 正确的公式是n(n-1)/2，而不是n(n+1)/2。 - templatetypedef

当然！出于某种原因，我一直认为n个中选k个是(n!)/(k!)。 - Jenny Shoars

你可以使用美妙的Wolfram Alpha网站来获取线索：http://www.wolframalpha.com/input/?i=approximate+%7Bn+choose+2%7D+at+n+-%3E+infinity - Erel Segal-Halevi

Answer 1

n个元素中选取2个的组合数为

n(n - 1) / 2

这等同于

n² / 2 - n/2

我们可以看到当n趋近于无穷大时，通过它们的比值来取极限，有n(n-1)/2 = Θ(n²)：

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

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

更一般地说：对于任何固定的常数k，n个元素中选择k个的组合数都是Θ(n^k)，因为它相当于

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

这是关于n的k次多项式，且具有非零的首项系数。

希望这有所帮助！

- templatetypedef

---

当然！出于某种原因，我一直认为n个中选k个是(n!)/(k!)。 - Jenny Shoars

@JennyShoars- 那肯定会让人感到困惑。希望这能澄清事情！ - templatetypedef

这将不会是 n^2/2 - n^2/2 吗？谢谢。 - Sachin Bahukhandi

你最后的说法只在 k = n / 2 时成立，在这一点上，组合函数分母中的 k 和 n-k 在约分中交换了优势，复杂度再次开始降低，最终降至 n choose n == 1。正确的概括是它是一个 theta(min(k, n-k)) 阶多项式。 - pjs

@pjs 很好的观点。我认为这取决于我们认为什么是变量，什么是固定的。如果k是一个固定的常数，n是一个变量，那么对于足够大的n值，我们将有n > k/2，正如所需的那样。（我们可以通过找到适当的c和n_0的值来使其正式化。） - templatetypedef

好的，这是一个很好的思考方式，因为实际上O()是一个描述缩放而不是工作预测。如果我们将n视为在某个点被缩放的参数，它将超过任何固定的k，在这种情况下，您的陈述保持不变。 - pjs