0

配列内のすべてのエントリが0から始まり、各ステップでカウンターを1ずつインクリメントする場合（0と1を反転することにより）、kインクリメントの償却コストはO（k）であることを既にご存知だと思います。

しかし、配列がnで始まる場合はどうなりますか？おそらく、k個の増分の複雑さはO（log（n）+ k）になっていると思います。これは、最初は1の最大数がlog（n）であるためです。

助言がありますか ？

前もって感謝します

4

1 に答える 1

1

あなたが正しいです。これを証明する方法は複数ありますが、そのうちの1つは潜在的な機能を備えています。このリンク（および他の多くのリンク）は、潜在的な方法を説明しています。ただし、教科書では通常、ポテンシャル関数の初期値が0である必要があります。そうでない場合を一般化してみましょう。

バイナリカウンタの場合、カウンタの潜在的な機能は1に設定されたビット数です。インクリメントすると、k + 1時間を費やしてk1を0に、1つを0から1に反転します。電位はk-1減少します。したがって、この増分の償却時間= ActualTime +（PotentialAfter-PotentialBefore）= k + 1-（k-1）= 2（定数）。

次に、ウィキペディアのリンクの「償却時間と実際の時間の関係」のセクションを見てください。

TotalAmortizedTime = TotalActualTime + SumOfChangesToPotential

SumOfChangesToPotentialは伸縮式であるため、FinalPotential-InitialPotentialと同じです。それで：

TotalAmortizedTime = TotalActualTime + FinalPotential-InitialPotential

これは次のようになります。

TotalActualTime = TotalAmortizedTime - FinalPotential + InitialPotential <= TotalAmortizedTime + InitialPotential

したがって、あなたが言うように、nで始まるk個の増分のシーケンスの合計時間はO（log n + k）です。

于 2012-11-02T08:51:04.960 に答える