償却された複雑さを理解しようとし、ネットでいくつかの検索を行いましたが、まだ適切なリソースを見つけることができませんでした.
それでは、償却された複雑さとは何か、また操作ごとにスプレイ ツリーでどのように O(lg n) になるかを説明できる人はいますか?
1958 次
1 に答える
1
挿入、削除など、スプレーツリーで実行される操作はすべて、コストがスプレー操作によって支配されます。したがって、表示されるノードで実行されるローテーションである表示操作のみのコストを考慮します。
The amortized function is given by a=c+3Rfinal(v)-3Rinitial(v)
ここで、a は償却コスト、c は実際のコスト、Rfinal はスプレイ操作後のランク、Rinitial はローテーション前のノードのランクです。ここで、S はその下にルートされているノードの数です)
ここで、展開するノードが葉である最悪のケースを考えます。したがって、初期ランクは 0 で与えられます。最上位に展開した後、つまりルート ノードとして、そのランクは log n になります。ここで、n はツリー内のノードの総数です。 .
a<= 2+3logn-0
O(logn).
于 2013-11-01T18:52:21.657 に答える