2進アルゴリズムの時間計算量

質問

ベキ乗計算を2進アルゴリズムで解いた場合の時間計算量を求める方法を教えてください。

x^nの時の時間計算量でn=2,3以外の時でn=2p,2p+1の時で場合わけして(pは整数)数学的帰納法で解いてあるのは見た事はあるのですが、どこからその仮定を持ってきたのか見当がつきません。
どうかお願いします。

n>3のときの時間計算量kは　k<=(2*log(n))-1
となっていました。

回答No.3

Tacosan · ベストアンサー

すみません, 想像ついてください.... というのも不親切なので, もうちょっとだけ:
まず, T(n) に関して
T(2) = 1, T(3) = 2, T(n) ≦ T([n/2]) + 2
という関係があります ([x] は x を超えない最大の整数). 漸化式の方を k 回繰り返すと
T(n) ≦ T([n/2^k]) + 2k
となりますが, [n/2^k] < 4 だとこの時点で漸化式の適用が終了し,
[n/2^k] = 2 なら T(n) ≦ 2k+1,
[n/2^k] = 3 なら T(n) ≦ 2k+2
です. ここで次のように場合分けして考えます:
2^k×2 ≦ n < 2^k×3 のとき. このとき k ≦ log n - 1 なので
T(n) ≦ 2k+1 ≦ 2(log n - 1) + 1 = 2 log n - 1.
2^k×3 ≦ n < 2^k×4 のとき. このとき k ≦ log n - log 3 ≦ log n - 1.5 なので
T(n) ≦ 2k+2 ≦ 2(log n - 1.5) + 2 = 2 log n - 1.
よっていずれの場合でも T(n) ≦ 2 log n - 1.
証明としてはこれでもだいたいいいんだけど, 厳密にいくならここから帰納法で.

回答No.4

bender

すでによい回答がでているのですが、以下のように考えることもできるかと思います。

「2進アルゴリズム」というのは、xのn乗（x^n）を計算する際に、nが偶数、奇数のとき、それぞれ、
x^n=x^(2×m)=(x^m)×(x^m)、
x^n=x^(2×m+1)=(x^m)×(x^m)×x
のようにx^1になるまで繰り返し「分解」して考える方法のことかと思います。
また、「時間計算量」というのは、このときの掛け算の回数ではないでしょうか。

その場合、（実際にいくつかの場合に「分解」してみればわかることですが、）x^nは先に書いた分解方法でfloor(log_2(n))回分解できる（つまり、nは2でfloor(log_2(n))回割ることができる）ことがわかります。例えばn=14のときであれば、floor(log_2(14))=floor(3.807...)=3回の分解、具体的には、
1回目： x^14= x^7 × x^7　（このとき、掛け算（×）が1回）
2回目： x^7 = x^3 × x^3 × x　（さらに掛け算が２回）
3回目： x^3 = x^1 × x^1 × x　（さらに掛け算が２回）

以上の例では、分解の1回目、2回目、3回目にそれぞれ、掛け算（×）を1回、2回、2回使っているので、計5回（1+2+2回）の掛け算でx^14が求められることになります。

ところで、（一番始めに書いた偶数、奇数のときの分解方法をみればわかるように）一回の分解についていえば、掛け算は多くても2回しかでてきません。そこで一般に、掛け算の回数の合計は、せいぜい「２×分解の回数」であることがわかります。つまり、k<=2×floor(log_2(n))。　...(A)

このまま floor をとると、k<=2×floor(log_2(n))<=2×log_2(n)ですが、もう少し考えると、n=7, 15, 31, 63, ...のように、n=2^m-1で表される数（2進数で表したとき全桁１になるような数）「以外」の数についていえば、x^nを繰り返し分解する際に、掛け算が（2回でなく）１回でよい分解（先のn=14の例では、（2、3回目のようではなく）１回目の分解）が必ず１度以上でてくるとわかります。そこでこのとき（n=2^m-1で「ない」とき）の掛け算の合計は、せいぜい「２×（分解の回数－１）＋１」、つまり、k<=2×(floor(log_2(n))-1) + 1 = 2×floor(log_2(n))-1 <= 2×log_2(n)-1とわかります。　...(B)
さらに、n=7, 15, 31, 63, ...についても、nがこれらの数のときはいつでも2×floor(log_2(n))<=2×log_2(n)-1がいえるので（省略）、先の(A)とあわせて考えると、やはり、k<=2×floor(log_2(n)) <=2×log_2(n)-1 といえます。　...(C)
そこで(B)と(C)より、与えられたnの範囲ではk <= 2×log_2(n)-1がいえると思います。

回答No.2

Tacosan

指数が n である場合の乗算の回数を T(n) とします.
計算方法から, すぐに
T(2n) = T(n) + 1,
T(2n+1) = T(n) + 2
であることがわかります. この式は「n が 2倍になると 乗算の回数がたかだか 2回増える」という意味です. なので, T(n) = 2 log n + c (c は定数) という形だろうと想像がつきます. そこでこの c を決めるために n = 2, 3 で考えると
T(2) = 2 log 2 + c = 2 + c = 1,
T(3) = 2 log 3 + c = 3.1... + c = 2
となります. ということで, c = -1 とおくと n = 2, 3 に対して T(n) ≦ 2 log n - 1 がいえます.
あとは帰納法でがんばる.

お礼

回答ありがとうございます。
>「n が 2倍になると 乗算の回数がたかだか 2回増える」という意味です. なので, T(n) = 2 log n + c (c は定数) という形だろうと想像がつきます

想像がつきません(笑)
どうやって見当をつければよいのか教えてください。
あと、c=-1と置いた理由も分かりません。

回答No.1

Tacosan

「その仮定」って何?

補足

n>3のときの時間計算量kは　k<=(2*log(n))-1
という仮定です。