問題タブ [amortized-analysis]

左から右に格納されたリストとして表示できる抽象データ型があり、次の操作が可能です: プッシュ: リストの左端に新しいアイテムを追加する ポップ: リストの左端にあるアイテムを削除する プル: リストの右端のアイテムを削除します

プッシュ、ポップ、またはプル操作の償却時間が一定になるように、3 つのスタックと一定の追加メモリを使用してこれを実装します。スタックには、isEmpty、Push、および Pop という基本的な操作があります。

償却された時間とは、「この時間を費やすと、別のブロックを費やして、後で使用するために時間の銀行に保存できる」ことを意味します。各プッシュ操作と同様に、一定時間の 3 つのブロックを費やすため、要素がプッシュされるたびに、一定時間の 2 つの余分なブロックがあります。

たとえば、O(n) のアルゴリズムと、償却された O(n) のアルゴリズムがあるとします。厳密に言えば、非償却アルゴリズムは常に償却アルゴリズムと同じかそれよりも高速であると言えますか? または、償却バージョンを好む理由はありますか (コードの単純さや実装の容易さなどを無視します)?

ウィキペディアの素集合フォレストの和集合/検索アルゴリズムの内訳は次のとおりです。

• ばらばらなばらばらの森... ( O(n))
  • ... ランクごとに結合 ... (現在は に改善O(log(n))
    • ...パス圧縮あり（現在O(a(n))、効果的に に改善されていますO(1)）

ランクによる結合を実装するには、各ノードがrank比較のためにフィールドを保持する必要があります。私の質問は、ランクによる結合はこの追加スペースの価値があるかということです? ランクによる結合をスキップして、代わりにパス圧縮を行うとどうなりますか? それは十分ですか？現在の償却複雑度は?

---

O(log(n)パス圧縮 (償却された複雑さ) のないランクによる結合は、ほとんどの実用的なアプリケーションに十分であることを意味するコメントが作成されます。正解です。私が求めているのは逆です: ランクによるユニオンをスキップして、代わりにパス圧縮のみを行うとどうなりますか?

ある意味で、パスの圧縮は、ランクごとの結合を改善するための追加の手順であり、そのため、その追加の手順を省略しても悲惨な結果を招くことはありません。しかし、ランクによる結合はパス圧縮に必要な中間ステップですか? それをスキップして直接パス圧縮に進むことはできますか?

---

また、ランクによる結合がなければ、結合が繰り返されると連結リストのような構造が作成される可能性があることも指摘されました。これは、単一パスの圧縮操作がO(n)最悪の場合にかかる可能性があることを意味します。もちろん、これは将来の運用に影響を与えるため、多くの運用で償却したときにこれがどのように機能するかが、私がより興味を持っていることです.

簡単な例として、動的配列の特定の実装では、配列がいっぱいになるたびに配列のサイズを 2 倍にします。このため、配列の再割り当てが必要になる場合があり、最悪の場合、挿入に O(n) が必要になる場合があります。ただし、n 個の挿入のシーケンスは常に O(n) 時間で実行できます。残りの挿入は一定時間で実行されるため、n 個の挿入は O(n) 時間で完了できます。したがって、操作ごとの償却時間は O(n) / n = O(1) です。――ウィキより

しかし、別の本では:各倍加には O(n) の時間がかかりますが、その償却時間はまだ O(1) であるため、めったに発生しません。

まれな状況がWikiの説明を推測していると誰かが教えてくれることを願っていますか? ありがとう

スプレイ ツリーについて読んでいるときに、ウィキペディアでスプレイ ノード 'X' のランクと償却コストに関する表現を見つけました。{ジグジグまたはジグザグ操作の償却コストを次のように制限できます。

ここで、x はルートに向かって移動されるノードであり、添字 "f" と "i" はそれぞれ操作の後と前を示します。スプレー操作全体を合計すると、これは O(log n) である 3(rank(root)) にテレスコープされます。ジグ操作は多くても 1 つなので、これは定数を追加するだけです。}

私はこれを解釈することができません。上記の詳細を説明してください。可能であれば、いくつかの例を挙げてください。

スプレー ツリーの他の定理の説明へのリンクを提供してください。

ありがとう

std :: vectorの後ろ（push_back）での挿入の分析をどのように行いますか？償却時間は挿入ごとにO（1）です。特に、Stephan T Lavavejによるchannel9のビデオと、これ（17:42以降）で、Microsoftがこのメソッドを実装すると、ベクトルの容量が約1.5増加すると彼は述べています。

この定数はどのように決定されますか？

There is a sequence of n operations, The ith operation costs 2i if i is an exact power of 2, costs 3i if i is an exact power of 3, and 1 for all other operations.

Hi first up I want to say that it is a homework problem and I don't want you to solve it for me.

I have solved it using the aggregate method. For which I summed up the series of powers of 2 and series of powers of 3 and got amortized cost of 10. I then checked it using the accounting method, for really long sequences and it did not fail. But my problem is how to prove that it would never fail, I can show for as long sequence I want but it would still not guarantee that it would not fail some time after.

Also I tried solving it with the potential function method, this is where I am really stuck, to device a potential function I think you need to be really creative, I cant find some condition which states that at this point this would always hold, need some help there too.

Just some ideas about how to prove it in the accounting method and how to device a potential function should be enough. Thanks

コードの一部にベクトルを使用すると効率的なアプリケーションがあります。ただし、計算中にいくつかの要素を追跡する必要があります。Data.Vectors から O(n) 償却連結を取得できると聞いたことがあります (通常の配列成長トリックによって) が、私はそれを正しく行っていないと思います。したがって、次の設定があるとしましょう。

addこの場合、償却された O(n) 時間で実行されますか? そうでない場合、どうすればそれをadd行うことができますか (状態に保存する必要があり(forall s. MVector s Int)ますか?)。より効率的な実装方法はありますaddか?

友達、私の教授はフィボナッチ ヒープをカバーし、宿題を出しました。要件は通常、抽出後にあり、同じ次数のルートをリンクしてルート リストを圧縮する必要があります。配列インデックスを使用して、同じ次数の別の要素を見つけます。しかしここで、システムに配列インデックス機能がないことを想像してください。同じ償却時間を達成できるように、いくつかのデータ構造と追加のポインターを使用して抽出を実装します!!

私はこれについて頭を悩ませましたが、アイデアがありません。手がかりや入力はありますか???