漸近解析とどう違うのですか？いつ使用しますか、またその理由は何ですか。
私はこれらのようにうまく書かれているように見えるいくつかの記事を読みました：
http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf
http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf
しかし、私はまだこれらの概念を完全には理解していません。
それで、誰かが私のためにそれを単純化してくれますか？
償却分析では、1 回の呼び出しの最悪のケースで呼び出しの数を単純に乗算することはありません。
たとえば、必要に応じてサイズが 2 倍になる動的配列の場合、通常の漸近的分析では、すべての要素を拡張して新しい配列にコピーする必要があるため、項目を追加するコストは O(n) であると結論付けるだけです。償却分析では、成長する必要があるためには、n/2 個のアイテムが前回の成長以降成長を引き起こさずに追加されている必要があるため、アイテムの追加には実際には O(1) しかかかりません (O(n) のコストはn/2 アクションで償却)。
償却分析は「平均パフォーマンス」と同じではありません。償却分析は、非常に多くのアクションを実行した場合にパフォーマンスがどうなるかを確実に保証します。
「何」に対する答えはたくさんありますが、「なぜ」に対する答えはありません。
誰もが言っているように、漸近分析は、特定の操作のパフォーマンスが大規模なデータ セットにどのようにスケーリングするかに関するものです。償却分析は、大規模なデータ セットに対するすべての操作のパフォーマンスの平均がどのようにスケーリングされるかについてです。償却分析は、漸近よりも悪い境界を与えることはなく、時にははるかに良い境界を与えることもあります。
より長いジョブの合計実行時間に関心がある場合は、おそらく、償却分析のより適切な境界が重要です。そのため、スクリプト言語 (たとえば) は、コストのかかる操作であっても、配列やハッシュ テーブルを何らかの要因で拡大しても問題ありません。（成長はO(n)操作になる可能性がありますが、償却されるのはO(1)、めったに行わないためです。）
リアルタイム プログラミングを行っている場合 (個々の操作は予測可能な時間内に完了する必要があります)、償却分析によるより良い境界は重要ではありません。平均的な操作が速かったとしても、切りすぎてしまう前に戻って帯鋸を調整するのに間に合わなかった場合は問題ありません...
あなたのケースでどちらが重要かは、プログラミングの問題が正確に何であるかによって異なります。
この用語は、アルゴリズムが操作するデータ (入力) が、「データを大きくしても結論が変わらないほど十分に大きい」という仮定の下でのアルゴリズムのパフォーマンスの分析を指します。入力の正確なサイズを指定する必要はありませんが (上限のみが必要です)、データセット自体を指定する必要があります。
ここまでは、分析方法についてのみ説明してきたことに注意してください。どの量を分析しているか (時間の複雑さ? 空間の複雑さ?) を正確に指定していません。また、関心のあるメトリック(最悪のケース? 最良のケース? 平均?) も指定していません。
実際には、漸近解析という用語は一般に、アルゴリズムの時間の複雑さの上限を指します。つまり、総実行時間で測定された最悪の場合のパフォーマンスであり、big-Oh 表記で表されます (たとえば、並べ替えアルゴリズムは となる場合がありますO(nlogn))。
この用語は、最悪のシナリオを対象とする特定の一連の操作に基づくアルゴリズム パフォーマンスの分析を指します。 ）。この分析を実行するには、入力のサイズを指定する必要がありますが、その形式について仮定する必要はありません。
簡単に言うと、償却分析とは、入力の任意のサイズを選択してから、アルゴリズムを「実行」することです。入力に依存する決定を下さなければならないときはいつでも、最悪のパスが取られます¹。アルゴリズムが完了するまで実行された後、計算された複雑さを入力のサイズで割り、最終結果を生成します。
¹注: 正確には、理論的に可能な最悪のパスです。容量が使い果たされるたびにサイズが動的に 2 倍になるベクトルがある場合、「最悪の場合」とは、挿入がシーケンスとして処理されるため、挿入ごとに 2 倍にする必要があると想定することを意味しません。入力が未知のままであっても、可能な限り多くの「さらに悪い」ケースを数学的に排除するために、既知の状態を使用することが許可されています (実際に使用する必要があります) 。
漸近分析と償却分析の決定的な違いは、前者は入力自体に依存するのに対し、後者はアルゴリズムが実行する一連の操作に依存することです。
したがって：
アルゴリズムの償却分析を理解するために私がこれまでに見つけた最良の参考文献は、Introduction to Algorithms、第 3 版、第 17 章「Amortized Analysis」にあります。すべてがそこにあり、Stack Overflow の投稿で見つけられるものよりもはるかによく説明されています。その本はまともな大学の図書館で見つけることができます。
通常の漸近分析では、問題のサイズの関数として、個々の操作のパフォーマンスを漸近的に調べます。O() 表記は、漸近分析を示すものです。
償却分析 (漸近分析でもあります) は、共有データ構造に対する複数の操作の合計パフォーマンスを調べます。
違いは、償却分析では通常、M 操作に必要な合計計算が、個々の操作の最悪のケースの M 倍よりも優れたパフォーマンスを保証することを証明することです。
たとえば、サイズ N のスプレー ツリーに対する個々の操作には、最大で O(N) の時間がかかる場合があります。ただし、サイズ N のツリーでの M 操作のシーケンスは、O( M(1+log N) + N log N ) 時間に制限されます。これは、操作あたりおおよそ O(log N) です。ただし、償却分析は「平均的なケース」の分析よりもはるかに厳密であることに注意してください。可能な操作のシーケンスが漸近的な最悪のケースを満たすことを証明します。
償却分析では、ルーチンを何度も実行した場合の総コストと、そこで得られるメリットを扱います。たとえば、ソートされていないn個のアイテムの配列で単一の一致を検索すると、最大n回の比較が必要になる可能性があるため、o（n）の複雑さがあります。ただし、同じ配列でm個のアイテムが検索されることがわかっている場合、タスク全体を繰り返すと、複雑さがO（m * n）になります。ただし、事前に配列を並べ替えると、コストはO（n log（n））になり、連続検索では、並べ替えられた配列に対してO（log（n））のみが必要になります。したがって、このアプローチを採用したm個の要素の合計償却コストはO（n * log（n）+ m * log（n））です。m> = nの場合、これは、ソートしない場合のO（n ^ 2）と比較して、事前ソートによるO（n log（n））に相当します。したがって、償却原価はより安くなります。
簡単に言えば、早い段階で少し余分に費やすことで、後で大幅に節約できます。