C++でのカウンターの増分の償却分析

償却分析 一連の操作では、実行時間、つまりシーケンスに必要な平均時間を決定するために使用されます。 Inは、常に平均的なケースのシナリオをとるとは限らないため、アルゴリズムで実行された平均的なケースの分析として扱うことはできません。分析の最悪のシナリオとして発生する場合があります。したがって、償却分析は、シーケンス内の複数の操作の最悪の場合の分析として扱うことができます。ここでは、各操作を異なる方法で実行するためのコストが高くなります。この問題は、バイナリカウンターを使用した一般的なビューです。

概念を明確にするために、C++プログラミング言語での動作と実装を見てみましょう。

kビットのバイナリカウンタは、最初に値が0である長さkのバイナリ配列を使用して実装されます。この値で、インクリメント操作が複数回実行されます。バイナリ8ビット配列が実行されたインクリメント操作でどのように動作するかを次に示します。

最初は、00000000> 00000001> 00000010> 00000011> 00000100> 00000101>....>11111111。

このロジックは、数値の最後のビットから最初の0が発生するかどうかをチェックし、それを1に反転し、それに続くすべてのビットを0に反転します。

例

#include <iostream>
using namespace std;
int main(){
   int number[] = {1,0,0,1,0,1,1,1};
   int length = 8;
   int i = length - 1;
   while (number[i] == 1) {
      number[i] = 0;
      i--;
   }
   if (i >= 0)
   str[i] = 1;
   for(int i = 0 ; i<length ; i++)
   cout<<number[i]<<" ";
}

出力

1 0 0 1 0 0 0 0

この問題では、各操作のコストは一定であり、ビット数に依存しません。

ここで、シーケンスのコストの漸近解析はO（n）です。

n回の操作で実行されるフリップの総数は-n+ n / 2 + n /4+…..+n / k ² フリップ数のk。

これは、分母にHPが含まれるGPです。

フリップの合計

合計=n+ n / 2 + n /4+…..+n / k ²

現在、芳香化された運用コストは O（n）/ 2n =O（1）です。

順序はO（1）であり、数値のビット数nに比例しません。