2

二乗による累乗が O(log n) 乗算になる方法がわかりません。

log n 以上の乗算を行うことになるようです (n は指数のサイズです)。

例：

              power(2,8)
       /                       \
     pow(2,4)        *          pow(2,4)
    /        \                 /        \      
pow(2,2) * pow(2,2)          pow(2,2) * pow(2,2)
   /               \             /              \
 p(2,1)*p(2,1) p(2,1)*p(2,1)  p(2,1)*p(2,1)    p(2,1)*p(2,1)

これは、通常の累乗と同様に、7 つの乗算です。

私が試した方法は以下の3つです。

long pow(int base, int exp)
{
  if(exp == 1)
    return base;
  else
    return base * pow(base, exp-1);
}

long pow2(int base, int exp)
{
  if(exp == 1)
    return base;
  else if(exp == 0)
    return 1;
  else
    if(exp % 2 == 0)
      return pow2(base * base, exp/2);
    else
      return base * pow2(base * base, exp/2) ;
}

long pow3(int base, int exp)
{
    if(exp == 1)
        return base;
    int x = pow2(base,exp/2);
        if(exp%2 == 0)
            return x*x;
        else
            return base*x*x;
}

再帰が底をつくと、同じ数の乗算が実行されるようです...

4

3 に答える 3

3

結果を保存し、分岐を再計算しないため、1 つの分岐のみを考慮する必要があります。次の乗算のみが実際に行われます。

              power(2,8)
       /                       \
     pow(2,4)        [*]        pow(2,4)
    /        \                 /        \      
pow(2,2) [*] pow(2,2)        pow(2,2) * pow(2,2)
   /               \             /              \
 p(2,1)[*]p(2,1) p(2,1)*p(2,1)  p(2,1)*p(2,1)    p(2,1)*p(2,1)
于 2013-08-15T09:57:05.443 に答える
2

二分木を表示していますが、再帰関数は自分自身を 2 回呼び出すのではなく、1 回だけ呼び出すため、単一の logN パスのみをトラバースしています。

また、このアルゴリズムでは、再帰はばかげています (遅く、複雑で、壊れやすい)。指数のビットをループするだけです：

long pow(long base, int exp) {
    long result = 1;
    while (exp > 0) {
        if (exp & 1) result *= base;
        exp >>= 1;
        base *= base;
    }
    return result;
}
于 2013-08-15T10:06:13.620 に答える
1

例 2^8 を見てみましょう。最初のステップでは、2^4 を計算する必要があります。結果が得られたら、それ自体を掛けるだけです。結果はすでにわかっているので、ツリー全体を計算する必要はありません。サンプルツリーを見てみましょう。この場合、一番左のツリーのみを計算する必要があります。つまり、2^4、2^2、2^1 のみを計算し、その結果を使用して 2^8 を取得します。

また、関数は次のようになります。

int power(int base, int power) {
    if (power == 0)
        return 1;
    if (power == 1)
        return base;
    int result = power(base, power / 2);
    result *= result;
    if (power % 2 == 1)
         result *= base;
    return result;
}
于 2013-08-15T09:56:09.220 に答える