バイナリカウンタの平均ケース時間複雑度の増加

Question

私は、バイナリカウンタの償却分析ではなく、平均ケース時間の複雑さを見出そうとしています。自分の時間複雑さのスキルを完全に確信しているわけではないので、下記の疑似コードの平均ケース分析が正しいことを確認したいと思います。

kを配列の長さとします。

Increment(Array) 
    i = 0 
    while i < k and Array[i] == 1 
     Array[i] = o 
     i = i + 1 
    if i < k 
     Array[i] = 1 

平均所要時間を調べるために、1回の実行あたりに平均ビット量が反転することがわかりました。結果として、これは、kの場合にO（1）に等しいO（2 + k /（2^k））であることがわかりました。

これは正しい平均実行時間ですか？そうでない場合は、どうすればこの問題に近づくでしょうか？私は、各入力を想定してい

Answer 1

これは、各ビットが独立で又は確率1/2とオフになっていることを意味

発生する同じ確率を有します。

geometric distributionは、複雑さに関する関連性の高いディストリビューションです。コインをひっくり返し、最初のテールの結果（実験することはもうありません）で実験を終了します。

ここでの幾何分布の平均は正確に2です（上のリンクを参照するか、または基本原理から導き出します）。したがって、平均複雑度は実際にO（1）です。