空avlのツリーがあり、一連の順序付けられた数値 (1、2、... k) を挿入したい場合、複雑さはなぜO(k).
ありがとうございました
1 に答える
2
それは数学の問題なので、これが取り引きです
AVL ツリーには、ツリー内に n ノードを持つ要素を挿入するための log(n) の時間計算量があります。
あなたの質問から、挿入したい一連の数値（1,2,3、...、k）を使用すると、時間の複雑さは次のようになります
summation from i=1 to i=k of log(i)(つまり、log1 + log2 + log3 + ... + logk)
に等しい
log(k!)
にほぼ等しい
k*log(k)(スターリングの近似を使用して)
したがって、あなたの質問に答えるには、O(k) ではなく O(k log k) にする必要があります
于 2013-12-19T15:03:54.150 に答える