スプレーツリーの背後にある直観(自己バランスのとれた木)
-
27-10-2019 - |
質問
私は広さの木の基本を読んでいます。操作の償却コストは、n操作よりもo(log n)です。いくつかの大まかな基本的な考え方は、ノードにアクセスすると、それを根絶するためにそれを吸収するので、次にこれがすぐにアクセスされ、ノードが深くなるとツリーのバランスを強化するということです。
このサンプル入力に対して、ツリーがどのように償却o(log n)を実行できるかわかりません。
nノードのツリーがすでに構築されているとします。私の次のn操作はn読み取りです。深さnで深いノードと発言にアクセスします。これにはO(n)が必要です。確かに、このアクセスの後、ツリーがバランスが取れるようになります。しかし、最新のディープノードにアクセスするたびに言ってください。これはo(log n)以下になることはありません。次に、最初の費用のかかるO(n)操作を補償し、各読み取りの償却コストをO(log n)として償却するにはどうすればよいでしょうか?
ありがとう。
解決
分析が正しく、操作が正しいと仮定します O(log(n))
アクセスごとに O(n)
初めて...
あなたが常にボトムモストの要素にアクセスする場合(何らかの最悪のオラクルを使用して)、一連のシーケンス a
アクセスがかかります O(a*log(n) + n)
. 。したがって、操作ごとの償却コストは次のとおりです O((a*log(n) + n)/a)
=O(log(n) + n/a)
あるいは単に O(log(n))
アクセスの数が大きくなるにつれて。
これは、「償却されたパフォーマンス/時間/空間」とも呼ばれる漸近平均ケースのパフォーマンス/時間/空間の定義です。あなたは誤ってシングルだと思っています O(n)
ステップは、すべてのステップが少なくともあることを意味します O(n)
;そのようなステップの1つは、長期的には一定の作業にすぎません。 O(...)
実際に何が起こっているのかを隠しています。 [total amount of work]
/[queries]
=[average ("amortized") work per query]
.
これはo(log n)以下になることはありません。
それは得るために必要です O(log n)
平均パフォーマンス。直感を得るには、次のWebサイトが良いかもしれません。 http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml 具体的には画像 http://users.informatik.uni-halle.de/~jopsi/dinf504/splay_example.gif - 実行中に O(n)
操作で、検索したパスを動かして、それを木の上部に向かってスクランチします。あなたはおそらくそのようなものの数しか持っていません O(n)
ツリー全体がバランスが取れるまで実行する操作。
これがそれについて考える別の方法です:
不均衡なバイナリ検索ツリーを検討してください。あなたは費やすことができます O(n)
時間のバランスをとる。要素を追加しないと仮定します*、それはかかります O(log(n))
要素を取得するためのクエリごとの償却時間。バランスの取れたセットアップコストは、償却コストに含まれています。これは、答えの方程式で示されているように、あなたがしている無限の量によって消える(war星化される)一定であるため、償却コストに含まれています。 (*要素を追加する場合は、自己バランスをとるバイナリ検索ツリーが必要です。そのうちの1つはスプレーツリーです)