私は試験を終えたばかりで、質問の 1 つは要約されていました。
サイズが 1000 の空の配列が与えられた場合、配列に n 個の要素を挿入するための償却コストはいくらですか? 配列がいっぱいになったら、配列を 2 倍にする代わりに、1000 ずつ増やして、動的テーブルの場合と同様に、すべての要素を新しい配列にコピーします。
私は O(n) と答えましたが、自分の答えに自信がありません。2 倍の動的テーブルの償却実行時間が 2 であることはわかっていますが、一定のサイズになる動的テーブルに関する情報はあまり見つかりませんでした。
初期サイズを A、増分も A、N 個の成長ステップがあるとします。すべてのステップで、要素をコピーする (必要に応じてメモリをクリアする) k*Size の基本操作が必要です。
コスト = k * (A + (A+A) + (A+2A) + ... + (A+(N-1) A)) = k (A*N +A*(1 + 2 + 3 +. .. + (N-1))) = k * (A*N + A*N*(N-1)/2) = O(N^2 * A) = O(N^2) (A が絶え間ない）
1 + 2 + 3 +... + (N-1) は等差数列の合計です
PS 配列コストを 2 倍にすると O(N)