私はスプレー木の基本を読んでいます。ある操作の償却原価は、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)あなたは誤って、1つのステップがすべてのステップが少なくともあることを意味すると考えています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))をフェッチするためにクエリごとに償却された時間がかかります。バランス設定コストは、実質的に定数であるため、償却コストに含まれます。これは、回答の式に示されているように、実行している作業の量が無限になると消えます（小さくなります）。（*要素を追加する場合は、自己平衡二分探索木が必要です。そのうちの1つはスプレー木です）
