我将展示log (n!) = Θ (n· log (n))。
给出了一个日志，即我应该用nn表示上界，并用(n/ 2)(n/ 2)表示下界。
解决这个问题的正确方法是什么？我应该画递归树吗？没有什么递归的，所以这似乎不是一个可能的方法。
375
记住
log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)
你可以得到上限
log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
= n*log(n)
你可以通过在扔掉前半部分后做类似的事情来获得下限：
log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n)
= log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
>= log(n/2) + ... + log(n/2)
= n/2 * log(n/2)
48
我意识到这是一个非常古老的问题，有一个公认的答案，但这些答案实际上都没有使用提示建议的方法。
这是一个非常简单的论点：
n!(= 1 * 2 * 3 *...* n) 是n数小于或等于n的乘积，因此小于n数的乘积，即n^n。
n!乘积中的一半数字-即n/2大于或等于n/2。因此，它们的乘积大于n/2数字的乘积，所有这些数字都等于n/2；即(n/2)^(n/2)。
记录整个日志以确定结果。
28
对不起，我不知道如何在 stackoverflow 上使用 LaTeX 语法。
14
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（88条）