累乗
pow0は遅いやつ。計算量はループをn回回すので、O(n)という。pow1は速いやつ。計算量はO(log n)らしい。
def pow0(x, n): value = 1 for i in range(n): value *= x return value def pow1(x, n): if n == 0: return 1 value = pow1(x, int(n / 2)) value *= value if n % 2 == 1: value *= x return value
ちなみに、自分のPCで速度を計ったら、下記だった。(python3内蔵のpow関数は、pow1と同じ速度だった) print(pow0(2, 1000000))は17.3秒 print(pow1(2, 1000000))は1.3秒
なんで、pow1の計算量はO(log n)なのか?
pow1を呼び出す度に、nを半分にしている(2のマイナス1乗を掛けてる)。nを2のk乗とおくと、pow1の呼び出し回数は、k回となる。よってO(k)となる、n = 2のk乗だから、k = log2 n。O()表記の場合、対数の底は無視するので、log n。