はじめに
今回は java の話ではなく..
たまたま面白いロジックに出会い、整理しておきたいと思いました.
純粋な python は、java と比べると処理が遅いですが、
見やすいため、簡単な書き方ゆえにロジックに時間を割愛できるため、アルゴリズムを書くときは python を使ったりします.
愛着を感じるのは、JVM 言語です -- 要らない情報でした.
ゴール
一つ一つ考えること 🙂
ことば
オーダー表記
n 個のデータに対する計算量です.
O(n) は、データが2倍、3倍 ... すると、計算量は2倍、3倍 ...
大量のデータを扱うため係数と定数は無視します.
O(3n - 4) == O(n)
O(log n) は O(log_n) です. _ は対数の底 2 のつもりで書きました.
データが2倍になると、計算量は log 2 （== 1) 増えます.
=> [外部リンク] 対数の底が省略できる理由
再帰
exit case は base case と呼ばれたり.
再帰を終える場合. 再帰の底です.
standard case は recursive case と呼ばれたり.
再帰し続ける場合. 標準的な行動です.
"再帰が終わる"という意味が伝わるので私は exit case という表現を選んだりします.
累乗そのもの
x^n = x \times x ...\times x \\
xをn回掛ける
とりあえず、正の整数を前提と考えていきます.
x が基数
n が指数
となります.
python の built-in だと
pow(x, n) # print(pow(2, 3)) 8
x ** n # print(2 ** 3) 8
になりますが、
目に見える形式で実装します.
def pow(x, n):
"""
O(n)
"""
result = 1
for _ in range(n):
result *= x
return result
x の数分、計算量が増えるので、計算量は O(n) です.
同じことを再帰で表現
def pow_r(x, n):
"""
O(n)
"""
if n == 0:
return 1 # exit case
else:
return x * pow_r(x, n - 1) # standard case
再帰ケースで指数 n を一つずつ減らして行き、n が 0に至ると、
2^0 = 1
なので、再帰から抜け出します.
掛け算の量を減らす
基本的な考え方はこうです.
x が n 個あったら、n 回計算する.
つまり n を減らすためには、指数を小さくしていくことが考えられます.
まず指数を半分に減らす(再帰)
① n が偶数の場合
x^n = (x^2)^\frac{n}{2}
② n が奇数の場合
x^n = x \times ((x^2)^\frac{n-1}{2})
例
n が偶数の場合、n を半分にします.
2^{20} = 4^{10}
4^{10} = 16^{5}
n が奇数のときは、1を引いて n を半分にします.
1を引いたので、引いた分を分離して係数にします.
16^{5} = 16 \times 256^{2}
改めて書き直すとこうなりました.
2^{20} = 16 \times 256 \times 256 \times 1
2を20回掛けていた20段階の乗算が、4段階に減りました.
def pow_r(x, n):
"""
O(log n)
"""
if n == 0: # exit case
return 1
if n % 2 == 0: # standard case ① n is even
return pow_r(x ** 2, n // 2)
else: # standard case ② n is odd
return x * pow_r(x ** 2, (n - 1) // 2)
// は切り捨て除算の演算子なので、standard case ② は
return x * pow_r(x ** 2, n // 2)
と本来は n - 1 が n と省略できます.
奇数 n を 2で割って切り捨てる == 奇数 n から 1を引いて2で割る
であるためです.
各段階ごとに掛け算の数を半分減らしていくため、計算量は O(log n)です.
使用するスタックメモリの領域も減らす(反復)
しかし、この形の再帰は、呼び出しのたびに(深くなるたびに)使うスペースの数も増えていきます.
ということで、関数内でのみ使う 変数 K を新たに設けます.
変数なので本来なら小文字が好ましいですが、見やすくしたいので...
指数 n が奇数のケースで、指数から 1 を減らして指数を半分にする際に、
基数 x が分離されました. ぽん.
x^n = x \times ((x^2)^\frac{n-1}{2}) \\
その x を別途記録して係数として K に溜めていきたいと思います.
make it work first
def pow_k(x, n):
"""
O(log n)
"""
if n == 0:
return 1
K = 1
while n > 1:
if n % 2 != 0:
K = K * x
x = x ** 2
n = (n - 1) // 2
else:
x = x ** 2
n = n // 2
return K * x # 指数を割り続け n が 1 に至ったら終了
2の20乗の計算で、K と x が return される時点での値は、K = 16, x = 65536 となります.
n が奇数になるケースはこの n==5 の段階の
16^{5} = 16 \times 256^{2}
16 のみでしたね.
きれいきれい
def pow_k(x, n):
"""
O(log n)
"""
if n == 0:
return 1
K = 1
while n > 1:
if n % 2 != 0:
K *= x
x *= x
n //= 2
return K * x
こっちの方が
- 指数が奇数の場合分離した係数を別途溜める
- 各段階で掛け算の量を半分に減らす
が見やすくなったかもしれません.
おわりまして
よりよい方法、よりよい説明、ご指摘や補足など、随時教えてくださいませ.