私はそのログnを知っています！O(nlogn) の複雑さを与えますが、上記を拡張するにはどうすればよいですか? 2 つ目は (nlogn)! に簡略化できます。これについて明確にしてください。
質問する
809 次
2 に答える
2
更新(N ln N)!：いいえ、 2番目の式では使用できません. その理由は、最初のケースを使用して以下に説明されます。
スターリング近似の対数バージョンでは、次のようになります。
ln(z!) = (z+1/2) ln z - z + O(1)...
余分なzものはここに保持されていることに注意してください。理由はすぐに明らかになります。ここx = log Nで、
(ln N)! = x! = exp(ln x!)
~ exp((x+1/2) ln x - x) = x^(x+1/2) exp(-x)
= (ln N)^((ln N)+1/2) / N
保持した余分な項は の逆であることが判明しましたN。何かの exp を単純に破棄することはできないため、複雑さに影響を与えることは間違いありません。g(N)上記の近似を表すとf(N) = (ln N)!、そしてlim f(N)/g(N) = sqrt(2 pi) < inf、そうf = O(g)
について(ln N!)!は、少し複雑です。私は mathematica を使用して極限をチェックしました。
ln(z!) ~ (z+1/2) ln z - z + ln(sqrt(2pi))
で十分です。いつ停止できるかについての一般的なルールはありません。また、一般に、有限項のみを使用することはできない場合があります。しかし、この場合は可能です。
-z緩い境界のみが必要な場合は、最初の式について、項を実際に捨てることができます(z+1/2) ln z > (z+1/2) ln z - z。
于 2013-08-19T16:05:58.503 に答える