これはバイナリカウンタの償却分析に関するものです。配列内のすべてのエントリは0から始まり、各ステップで単純にカウンタをインクリメントします。バイナリカウンタ償却分析について
ここで著者は以下のように言及しています。
現在のカウントで1ビットの数に等しい可能性のある関数を使用しています。
質問1：上記の声明は何を意味していますか？私は
そして他の問題は、それが
として言及されたn +（N/2）+（N/4）+ ---は、[最大2Nある分析です。私たちはどうやって2nの結果を得ましたか？
ありがとうございます！
この例のインクリメントのコストは、実行するビットフリップの数です。
I.e. 3（0b11）から4（0b100）まで増やすと3のコストがかかります（3つの位置はすべて反転します）。
ここでは、時間の量がビットフリップの数に依存し、したがって数値によって異なるため、アルゴリズムが一定に償却されるとは言えません。
1.
これは理にかなっています。これは、各ビットが1であるため、将来のインクリメント操作では、ある時点で0に変更する必要があるためです。したがって、最後のビットよりも多くを反転する必要があるインクリメントが発生するたびに、値の可能性を利用します。
償却分析を続けると、潜在的な可能性は常に1ずつ増加し、インクリメント操作ごとに反転した1ビットごとの可能性が低下することがわかります。これを各操作で組み合わせると、コストは2になります。a）0からa1に反転、b）潜在的に1を保存します。 0より前にすべてのものを反転すると、が支払われ、潜在的可能性を使ってが支払われます。
これは非常によくある質問です。そのようなhere in PDFの例がコスト面で非常によく説明されています。
図からわかりやすいが、この場合は最小の単位に対応する別の関数を使用して、そこから出てくる合理的な値に等しくすることができるpdfの1ビットフリップなどの関数は$ 1と等価です。潜在的な機能は、分析の実行を容易にします。それは0から始まり、負でなければならない。
ちょうど等比数列を使用するここでa = 1およびr = 1/2。幾何学的な進展の合計は
a(1-r^{n})/(1-r).
Here it is (1-(1/2)^{n})/(1-(1/2)) = 2*(1- (1/2)^n).
As n goes to infinity, it becomes 2.
です。申し訳ありませんが、配列の1ビットの平均数ですか？ – venkysmarty