数のサイズのO記法について

質問

代数学の勉強をしています。O記法についてわからないところがあります。

「a,b∈N,a,b≦nとしk:=[log(n)]+1とする。
加法a+bの計算に対するビット演算の数はO(k)で
乗法a・bに対してはO(k^2)である。
もし高速乗算アルゴリズムが使用されれば、乗法
はO(klog(k))にまで改良することができる。」

とあるのですが、加法がO(k)、乗法がO(k^2)と表せるのはO記法の考え方からわかりました。
しかし、「高速乗算アルゴリズムが使用されれば、乗法はO(klog(k))にまで改良することができる」
というところがどうしてそうなるのかがわかりません。

※logの底は2です。

回答No.3

rinkun · ベストアンサー

No.2さんの意見は飛躍があると思う。
ちなみに実際に乗算を分割統治法で演算するアルゴリズムはO(klog(k))ではなくO(k^log(3))になる。
これはk桁の乗算はk/2桁の乗算3回に分割されるためである。

お礼

ありがとうございました。
参考になりました。

回答No.2

sunasearch

乗算アルゴリズムに限らず、べたな方法でO(k^2)のアルゴリズムは、改良によって、O(klogk)のアルゴリズムにできることが知られています。

イメージとしては、データ数ｋ(下記の例では8)に対して、

1111111
1111,1111
11,11,11,11
1,1,1,1,1,1,1,1

全体の問題を半分の大きさの問題に分割を繰り返して解く方法を考えると、繰り返しの回数がlogk(log8=3)回になることから、
データ数ｋ×繰り返し回数logk = klogkのオーダになると言った感じです。

お礼

ありがとうございました。
参考になりました。

回答No.1

rinkun

代数学というよりは演算量の理論の話ですね。
実際に多バイト長の乗算を高速に実行するアルゴリズムがあって、それを使うと桁数kに対してO(klog(k))になるんです。
具体的なアルゴリズムは高速フーリエ変換(FFT)に関して調べると出てきます。