問題タブ [amortized-analysis]

配列内のすべてのエントリが0から始まり、各ステップでカウンターを1ずつインクリメントする場合（0と1を反転することにより）、kインクリメントの償却コストはO（k）であることを既にご存知だと思います。

しかし、配列がnで始まる場合はどうなりますか？おそらく、k個の増分の複雑さはO（log（n）+ k）になっていると思います。これは、最初は1の最大数がlog（n）であるためです。

助言がありますか ？

前もって感謝します

二分探索木でn 個の挿入のシーケンスの償却コストを計算するにはどうすればよいですか? 入力シーケンスはランダムで、挿入ごとに 1 つのノードが追加されます。

私は現在、償却分析を読んでいます。アルゴリズムの平均または最悪のケースの動作を計算するために実行する通常の分析とどのように異なるかを完全に理解することはできません。誰かがソートなどの例で説明できますか?

答えだけでなく、物事がどのように機能するかを理解したいと思っています。私が持っているものを答えていますが、よくわかりませんし、テキストにはこの種の分析についてはあまり説明されていません。

これがスタックを実装する方法ではないことは十分承知していますが、これが私たちが与えられたシナリオです。

パートA

スタックを表す N 個の整数を含む (ソートされていない) 配列 a のスロット a[0] への挿入の最悪の場合、平均的な場合、および最良の場合の実行時間はどれくらいですか? シータ範囲を指定します。

パートB

すべての挿入が a[0] で行われる場合、スタックを表す最初は空の配列 a への N 個の整数の挿入の償却実行時間は? タイトな O バウンドを与えて、答えを説明してください。

インストラクターは、すべての挿入を a[0] に行っていること、およびこの「スタック」からの削除がないことを明確に示しました。

私の分析はこうです

仮定: a.length >> N

最良のケースは、空の「スタック」に挿入するときに発生する Theta(1) です。

最悪のケースは Theta(N) です。これは、挿入プロセスの一部として、a[0] の場所を空けるために N-1 要素をシフトする必要があるためです。

平均的なケースも Theta(N) です。なぜなら、常に N-1 要素をシフトする必要があるからです。

償却ケース

各挿入コストは (N-1) で、N 個の要素があるため、以下を使用します。

償却コストは、N^2 / N = O(N) になります。

私が抱えている問題は、これが簡単に見えることです。私は何かを見逃していますか、それともほとんど死んでいますか?

誰かが償却された複雑さを素人の言葉で説明できますか? 私はオンラインで正確な定義を見つけるのに苦労しており、それがアルゴリズムの分析とどのように関連しているのかわかりません. 外部から参照されたものであっても、役に立つものは何でも高く評価されます。

償却された複雑さが何を意味するのか完全にはわかりません。バランスのとれた二分探索木データ構造 (例: 赤黒木) を使用します。通常の検索のコストは当然 log(N) です。ここで、N はノードの数です。しかし、一連の m 回の検索を、たとえば昇順で実行した場合の償却後の複雑度はいくらになるでしょうか。log(N)/mだけですか？

提案。Stack のサイズ変更配列の実装では、空のデータ構造から始まる一連の操作に対する配列アクセスの平均回数は、最悪の場合でも一定です。

証明スケッチ: 配列を大きくする (サイズ N からサイズ 2N に) 原因となる各 push() について、N/2 - 1最後にスタック サイズを k に成長させた push() 操作を考えますN/2 + 2 to N。4N 配列アクセスを平均して N/2 配列アクセス (プッシュごとに 1 つ) で配列を成長させると、操作ごとに 9 配列アクセスの平均コストが得られます。M 操作の任意のシーケンスで使用される配列アクセスの数が M に比例することを証明することは、より複雑です。(アルゴリズム第 4 版第 1.4 章)

証明スケッチを完全に理解していませんでした。これを理解するのを手伝ってください。

コードフォースの問題を解決しています。社説によると、次のコードの複雑さは O(n) である必要があります。

ここで、height[i]は - 番目の丘の高さであり、は よりも高い右から 1i番目の丘r[i]の位置であり、height 配列の他の値の中で常に最大です。height[i]height[0]

私の質問は、内側の while ループが存在するにもかかわらず、コードの複雑さが O(n) であることをどのように保証できるでしょうか?

内側の while ループで、コードは>にr[i]なるまで値を更新します。更新の数は、高さの配列によって異なります。たとえば、非減少順でソートされた高さ配列の更新回数は、非増加順でソートされた高さ配列の更新回数とは異なります。(どちらの場合も、この問題では が常に最大であるため、を除く配列をソートします)。height[i]height[r[i]]height[0]height[0]

そして、このような入力データによって変化するアルゴリズムを分析する方法はありますか? 償却分析は答えの1つになりますか？

PS。私の質問をもっと明確にしたいと思います。ループ内に配列 r[] を設定します。そして、これはどうですか？配列height = {5,4,1,2,3}とi=1, ( r[2]=3, r[3]=42 は 1 より大きい最初の値であり、3 は 2 より大きい最初の値であるため) の場合、4 と 1 を比較し、4>1 であるため、比較を試み続けます。 4 と 2(= height[r[2]])、4 と 3(= height[r[3]])。この場合、r[1] を設定するために 4 回比較する必要があります。の場合とは比較回数が異なりますheight = {5,1,2,3,4}。コードの複雑さが O(n) であることを保証できますか? 見逃した場合はお知らせください。ありがとうございました。