提案。Stack のサイズ変更配列の実装では、空のデータ構造から始まる一連の操作に対する配列アクセスの平均回数は、最悪の場合でも一定です。
証明スケッチ: 配列を大きくする (サイズ N からサイズ 2N に) 原因となる各 push() について、N/2 - 1最後にスタック サイズを k に成長させた push() 操作を考えますN/2 + 2 to N。4N 配列アクセスを平均して N/2 配列アクセス (プッシュごとに 1 つ) で配列を成長させると、操作ごとに 9 配列アクセスの平均コストが得られます。M 操作の任意のシーケンスで使用される配列アクセスの数が M に比例することを証明することは、より複雑です。(アルゴリズム第 4 版第 1.4 章)
証明スケッチを完全に理解していませんでした。これを理解するのを手伝ってください。
これは一種の償却分析であり、push() などのリクエストが直接の原因ではない作業に対して請求し、誰も高すぎる料金を支払う必要がないことを示しています。つまり、行われた作業の平均コストは小さな。
この場合、スペースがなくなったときに配列全体をコピーする必要がありますが、これを行うとサイズが 2 倍になるため、頻繁にコピーすることはありません (サイズ 1、2、4、8、16 など)。ここでは、最後の配列コピー以降に実行された push() 操作に対して、各配列コピーを請求します。これは、push() 以外何もしない場合、各 push() はその後に発生する最初の配列コピーに対してのみ請求書を取得することを意味します。 ) の場合、償却原価は小さくなります。
配列がスペースを使い果たし、サイズが 2 倍になる前に配列のサイズが N である場合、この記事では、これには 4N の操作が必要であると述べていますが、これは合理的に聞こえます。これは、最後の倍加以降のすべての操作に分割されます。最後の 2 倍はサイズ N/2 からサイズ N だったので、約 N/2 あります。これにより、N/2 の push() 操作に分割された 4N の操作が得られるため、各プッシュは 8 の共有請求書を取得します。 push() ごとに 9 回の書き込みの平均コスト。