2

（単位コストではなく）ビットコストに関してアルゴリズムの時間計算量を研究するという概念に頭を悩ませようとしていますが、このテーマについては何も見つけることができないようです。

これが私がこれまでに持っているものです：

nビットの2つの数値の乗算と除算のビットコストは、任意の算術演算ではO（n ^ 2）です。

したがって、たとえば：

int number = 2;
for(int i = 0; i < n; i++ ){
    number = i*i;
}

O（log（n）^ 2 * n）のビットコストに関して時間計算量があります。これは、n回の乗算を実行し、ビットをi持っているためです。log(i)

しかし、通常のシナリオでは、入力に関して時間計算量が必要です。では、そのシナリオはどのように機能しますか？のビット数はi定数と見なすことができます。これにより、定数が大きくなることを除いて、時間計算量はユニットコストと同じになります（したがって、両方とも線形になります）。

加算、減算、比較、および変数の割り当てはすべてO（n）であり、任意精度の算術演算の場合、nはビット数です。

4

1 に答える 1

4

精度の低い算術演算（この例ではおそらく32ビットintの乗算など）では、乗算のビットコストは一定です。2を乗算するコストはint、O(32^2)単純な乗算アルゴリズムを使用することです（より良いアルゴリズムについては、こちらを参照してください）。O(1)これは、アルゴリズムを分析するときに人々が通常それについて言及することを怠るのと同じです。

ただし、任意精度の演算を使用する場合は、それが重要になります。の値を持つ任意の長さの数値がiビット単位で格納されている場合、ビットを使用しO(log(i))ます。したがって、コードスニペットのコストは次のようになります（ループが最大になるため、すべてが大きくならないO(log(n)^2 * n)という事実を使用しています）。inn

加算と減算に関しては、どちらもビットコストがであると言えますO(n)。ここnで、は小さい方のオペランドのビット数です。

于 2012-10-06T22:09:18.600 に答える