我被这个问题困住了。我认为这相当于证明 2m 选择 m 是 4 的 n 次方的大 theta，但仍然难以证明。
感谢@LutzL 的建议。我之前想到了斯特林的近似值。
问问题
2239 次
3 回答
3
O部分应该很容易。从 n 个元素中准确选择n /2 个元素是从n个元素中选择任意组合的特殊情况，即为这n个元素中的每一个决定是否选择它。
Ω部分更难。事实上，为中等大的n绘制 4 n / binomial(2 n , n )我没有看到任何迹象表明这会变平以保持在某个常数以下。直观地说，n越大，当你从n 个元素中随机选择一个，并且碰巧恰好选择了其中的n /2 个时，情况就越特殊。随着n的增加，该概率应该趋于零，这意味着 2 n应该总是比n选择n /2增长得快。您确定您正确理解了这部分任务吗？
于 2016-09-18T13:48:35.550 回答
2
您可以对阶乘使用斯特林公式。
n! = sqrt(2*pi*(n+theta)) * (n/e)^n
其中theta介于 0 和 1 之间，趋向于 0 的趋势很大。
于 2016-09-18T13:30:31.710 回答
2
不是 - 它是 Theta(2^n/sqrt(n))，实际上选择 (n, n/2) ~ 2^n/sqrt(pi * (n/2)) 作为 n->infinity)。见https://en.wikipedia.org/wiki/Central_binomial_coefficient
于 2016-09-19T01:58:54.850 回答