0

ここで同じ質問を見ました。彼らはこのように下限を証明しました

    log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) 
                                   >= log(n/2) + ... + log(n/2)
                                    = n/2 * log(n/2)

私の疑問は、下限が n log n 自体ではないのはなぜですか? または、他のより厳しい下限はありますか?. 具体的に n/2 * log(n/2) なのはなぜですか?

4

1 に答える 1

4

これは、それを証明するために使用されます。

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n) = Θ(n·log(n))

これを証明するには、Θ(n·log(n)) の上限と下限の両方を見つければ十分です。

下限

n/2 * log(n/2)

すでに Θ(n・log(n)) に対応しています。これは簡単に取得でき、関心のある Θ に属します。より厳密な下限を見つけることはより困難であり、必要ではありません。

この質問の完全な証明:

log(n!) = Θ(n・log(n))ですか?

于 2014-09-10T00:34:26.267 に答える