Pocket
LINEで送る

累乗

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。

参考:
再帰定義 (recursive definition)
[初心者向け] プログラムの計算量を求める方法

Pocket
LINEで送る


コメントください

関連記事

プログラミング

Go言語によるビットコインのフルノード実装btcdを調べる(2)

btcdを実行した際のプログラムの流れを最初から確認してみます。 se 続きを読む …

プログラミング

Go – leveldb

Goで使えるLevelDB。 syndtr/goleveldb ドキュ 続きを読む …

%d人のブロガーが「いいね」をつけました。