http://en.wikipedia.org/wiki/Dynamic_array#Performance
正確にはどういう意味ですか？
最後に挿入するのはO（n）だと思いました。たとえば、元の配列の2倍のスペースを割り当ててから、すべてのアイテムをその場所に移動して、最後にアイテムを挿入する必要があるからです。このO（1）はどうですか？
質問する
246 次
2 に答える
5
償却されたO（1）効率は、個々の操作にかなり時間がかかる場合でも、n回の挿入の実行時間の合計がO（n）になることを意味します。
すべてをコピーするために必要な作業のために、要素の追加にO（n）時間がかかる可能性があることは絶対に正しいです。ただし、配列は拡張されるたびに2倍になるため、コストのかかる2倍のステップは指数関数的に少なくなります。その結果、n個のインサートで行われる作業の合計は、O（n 2）ではなくO（n）になります。
詳細に説明すると、合計n個の要素を挿入するとします。ベクトルのサイズを変更するときに要素をコピーするために行われる作業の合計量は、最大で
1 + 2 + 4 + 8 +...+n≤2n-1
これは、最初に1つの要素をコピーし、次に2倍、次に2倍というようにコピーし、最悪の場合はn個の要素すべてをコピーするためです。この等比数列の合計は2n-1になります。したがって、多くてもO（n）要素がすべてのコピーステップにわたって移動します。n個の挿入を実行し、それらすべてにわたってO（n）の合計作業のみをコピーするため、償却効率は操作ごとにO（1）になります。これは、各操作にO（1）時間かかるという意味ではありませんが、n回の操作に合計O（n）時間かかるということです。
この背後にあるグラフィカルな直感、およびアレイを少しだけ増やすのではなく2倍にする理由については、これらの講義スライドを確認することをお勧めします。最後の方の写真は非常に関連性があるかもしれません。
お役に立てれば！
于 2013-01-13T20:32:46.783 に答える
4
分離された各再割り当てはO（N）です。しかし、次のN回の挿入では、何もする必要はありません。したがって、挿入あたりの「平均」コストはO（1）です。「費用は複数の事業にわたって償却される」と言います。
于 2013-01-13T20:27:44.973 に答える