algorithm - 一定償却時間

Question

アルゴリズムの時間の複雑さについて話すとき、「一定の償却時間」とはどういう意味ですか?

Answer 1

簡単な言葉で説明された償却時間：

操作を 100 万回行う場合、その操作の最悪のケースや最良のケースはあまり気にしません。気にするのは、操作を 100 万回繰り返したときに合計でどれだけの時間がかかるかです。 .

したがって、動作が非常に遅くても問題はありません。ただし、「たまに」がまれにしか発生しないため、速度が低下することはありません。基本的に償却時間とは、「多くの操作を行う場合に、操作ごとにかかる平均時間」を意味します。償却時間は一定である必要はありません。線形および対数の償却時間などを使用できます。

新しいアイテムを繰り返し追加する動的配列のマットの例を見てみましょう。通常、アイテムの追加には一定の時間がかかります (つまり、O(1))。ただし、アレイがいっぱいになるたびに、2 倍のスペースを割り当て、データを新しいリージョンにコピーし、古いスペースを解放します。割り当てと解放が一定時間で実行されると仮定すると、この拡大プロセスにはO(n)時間がかかります。ここで、n は配列の現在のサイズです。

したがって、拡大するたびに、前回の拡大の約 2 倍の時間がかかります。しかし、あなたはそれをする前に 2 倍も待っていました! したがって、各拡大のコストは、挿入間で「分散」することができます。これは、長期的には、m個の項目を配列に追加するのにかかった合計時間は であることを意味しO(m)、償却時間 (つまり、挿入ごとの時間) はO(1)です。

Answer 2

これは、時間の経過とともに、最悪のシナリオがデフォルトで O(1) または一定時間になることを意味します。一般的な例は、動的配列です。新しいエントリにすでにメモリを割り当てている場合、それを追加すると O(1) になります。割り当てていない場合は、たとえば現在の金額の 2 倍を割り当てて割り当てます。この特定の挿入はO(1) ではなく、別のものになります。

重要なのは、一連の操作の後、コストのかかる操作が償却され、それによって操作全体が O(1) になることをアルゴリズムが保証することです。

または、より厳密に言えば、

定数 c があり、長さ L の すべての一連の操作 (コストのかかる操作で終了する操作も含む) について、時間が c*L を超えないようにします ( Rafał Dowgird に感謝します) 。

Answer 3

3回繰り返し読んだ後、以下のウィキペディアの説明が役立つことがわかりました。

ソース: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

「ダイナミックアレイ

動的配列のプッシュ操作の償却分析

Java の ArrayList など、要素が追加されるとサイズが大きくなる動的配列を考えてみましょう。サイズ 4 の動的配列から始めた場合、4 つの要素をプッシュするのに一定の時間がかかります。ただし、5 番目の要素をその配列にプッシュすると、配列が現在のサイズの 2 倍 (8) の新しい配列を作成し、古い要素を新しい配列にコピーしてから、新しい要素を追加する必要があるため、時間がかかります。次の 3 つのプッシュ操作も同様に一定の時間がかかり、その後の追加では配列サイズをゆっくりと 2 倍にする必要があります。

一般に、サイズ n の配列への任意の数 n のプッシュを考えると、プッシュ操作はサイズ倍増操作を実行するのに O(n) 時間かかる最後のものを除いて、一定の時間がかかることに気付きます。合計 n 回の操作があったため、これの平均を取ることができ、要素を動的配列にプッシュするのにかかる時間が O(n/n)=O(1)、一定時間であることがわかります。」

単純な話としての私の理解では：

あなたがたくさんのお金を持っていると仮定してください。そして、あなたはそれらを部屋に積み重ねたいと思っています。そして、あなたは現在または将来必要なだけ長い手足を持っています。また、1つの部屋にすべてを埋める必要があるため、ロックが簡単です。

それで、あなたは部屋の端/隅に行き、それらを積み重ね始めます. それらを積み重ねると、ゆっくりと部屋のスペースがなくなります。しかし、あなたがいっぱいになると、それらを積み重ねるのは簡単でした. お金を手に入れた、お金を入れた。簡単。O(1)です。以前のお金を移動する必要はありません。

部屋のスペースがなくなると。もっと大きな別の部屋が必要です。ここで問題があります。部屋が 1 つしかないため、ロックも 1 つしか持てないため、その部屋にあるすべての既存のお金を新しい大きな部屋に移動する必要があります。だから、小さな部屋から大きな部屋にすべてのお金を移動します。つまり、それらすべてを再度スタックします。したがって、以前のお金をすべて移動する必要があります。つまり、O(N) です。（Nは前のお金の合計金額であると仮定）

つまり、N回までは1回の操作で簡単だったのですが、大きな部屋に移動する必要がある場合は、N回の操作を行いました。つまり、平均すると、最初は 1 回挿入され、別の部屋に移動する間にさらに 1 回移動します。合計 2 回の操作、1 回の挿入、1 回の移動。

狭い部屋でも N が 100 万のように大きいと仮定すると、N (100 万) に対する 2 回の操作は実際には比較可能な数ではないため、定数または O(1) と見なされます。

上記のすべてを別の大きな部屋で行い、再び移動する必要があると仮定します。それは今でも同じです。たとえば、N2 (たとえば、10 億) は、より大きな部屋での新しい金額です。

したがって、N2 があります (すべて小さい部屋から大きい部屋に移動するため、これには前の N が含まれます)。

必要な操作は 2 つだけです。1 つは大きな部屋への挿入、もう 1 つはさらに大きな部屋への移動操作です。

なので、N2（10億）でも、それぞれ2回の演算です。これは再び何もありません。したがって、定数、または O(1)

そのため、N が N から N2 などに増加しても、それほど重要ではありません。それは依然として一定であるか、または N のそれぞれに必要な O(1) 操作です。

---

ここで、N が 1 で、非常に小さく、お金の数が少なく、お金が 1 つだけ収まる非常に小さな部屋があるとします。

部屋にお金を入れるとすぐに部屋がいっぱいになります。

大きい部屋に行くときは、あと 1 枚のお金しか入らないと仮定して、合計 2 枚のお金を数えます。つまり、前に移動したお金ともう 1 つです。そしてまた埋まる。

このように、N はゆっくりと成長し、以前の部屋からすべてのお金を移動しているため、一定の O(1) ではなくなりますが、あと 1 つのお金しか収まりません。

100回後、新しい部屋は以前の100カウントのお金と1つの追加のお金に適合します。O(N+1) は O(N) であるため、これは O(N) です。つまり、100 または 101 の次数は同じであり、前の話とは対照的に、どちらも数百です。 .

したがって、これはお金 (変数) に部屋 (またはメモリ/RAM) を割り当てる非効率的な方法です。

---

そのため、2 のべき乗で、より多くの部屋を割り当てることをお勧めします。

1 番目の部屋のサイズ = 1 カウントのお金に
合う 2 番目の部屋のサイズ = 4 カウントのお金に
合う 3 番目の部屋のサイズ = 8 カウントのお金に
合う 4 番目の部屋のサイズ = 16 カウントのお金に
合う 5 番目の部屋のサイズ = 32 カウントのお金に
合う 6 番目の部屋のサイズ = お金のカウントに合う64 カウント
7 番目の部屋サイズ = 128 カウントのお金に
適合 8 番目のルーム サイズ = 256 カウントのマネーに
適合 9 番目のルーム サイズ = 512 カウントのマネーに
適合 10 番目のルーム サイズ = 1024 カウントのマネー に
適合
..
16 番目の部屋のサイズ = 65,536 カウントに適合
...
32 番目の部屋のサイズ = 4,294,967,296 カウントに適合
...
64 番目の部屋のサイズ = 18,446,744,073,709,551,616 カウントに適合

なぜこれが良いのですか？RAM のメモリ量と比較して、最初はゆっくりと成長し、後で速く成長するように見えるからです。

最初のケースでは、それは良いことですが、お金ごとに行われる作業の合計量は固定されており (2)、部屋のサイズ (N) とは比較になりません。最初のケースでそれほど多くのお金を節約できるかどうかによっては、十分に使用できない可能性がある大きな (100 万)。

ただし、最後のケースである 2 の累乗では、RAM の制限内で大きくなります。したがって、2 の累乗で増加すると、Armotized 分析は一定のままであり、現在の限られた RAM に適しています。

Answer 4

償却実行時間: これは、操作ごとに使用される時間またはメモリに関するアルゴリズムの複雑さの計算を指します。ほとんどの操作は高速ですが、アルゴリズムの操作が遅い場合に使用されます。したがって、償却された時間についてさらに学ぶために、一連の操作が調査されます。