algorithm - 動的配列の償却時間

Question

簡単な例として、動的配列の特定の実装では、配列がいっぱいになるたびに配列のサイズを 2 倍にします。このため、配列の再割り当てが必要になる場合があり、最悪の場合、挿入に O(n) が必要になる場合があります。ただし、n 個の挿入のシーケンスは常に O(n) 時間で実行できます。残りの挿入は一定時間で実行されるため、n 個の挿入は O(n) 時間で完了できます。したがって、操作ごとの償却時間は O(n) / n = O(1) です。――ウィキより

しかし、別の本では:各倍加には O(n) の時間がかかりますが、その償却時間はまだ O(1) であるため、めったに発生しません。

まれな状況がWikiの説明を推測していると誰かが教えてくれることを願っていますか? ありがとう

Answer 1

Amorized とは、基本的には操作数あたりの平均を意味します。

したがって、n 個の配列がある場合、再割り当てが必要になるまでn+1 個の項目を挿入する必要があります。

したがって、それぞれがO(1)を使用した n 回の挿入と、 O(n)を使用した別の挿入を実行したため、合計で2n 操作のコストがかかるn+1 アクションが得られます。

2n / n+1  ~= 1 

そのため、償却時間はまだO(1)です。

Answer 2

はい、これら 2 つのステートメントは同じことを言っています。Wiki はそれをより詳しく説明しているだけです。