0

挿入のコストが であるツリーを考えてみましょうO(log n)。空のツリーから始めて、N 個の要素を繰り返し追加するとします。総時間の複雑さを知りたいです。これは私がしました：

nb of operations in iteration i = log i
nb of operations in all iterations from 1 to N = log 1 + log 2 + ... + log N = log( N! ) 
total complexity =  O(N!) ~ O(N log N)

(スターリング近似http://en.wikipedia.org/wiki/Stirling%27s_approximationを参照)

これは正しいです？

4

1 に答える 1

2

はい、ほぼ正しいです。

小さな修正:i番目のステップでは、操作の数は ではありません log i。ほとんどの場合、これは無理数であるためO(log i)です。したがって、数学的に厳密な証明を行うには、もう少し努力する必要がありますが、要するに、あなたが書いたものが証明の本質です。

于 2013-09-05T08:33:59.007 に答える