-1 
#include<stdio.h>
#include<math.h>

int main() {
double n,p,ans;
while(scanf("%lf %lf",&n,&p)==2)
{
    ans=pow(p,(1/n));

    printf("%.0lf\n",ans);
}
return 0; 
 }

ここで ans を見つけるために使用されるアルゴリズムは何ですか。この pow() 関数の複雑さは何ですか?

4

2 に答える 2

7

C99 標準のセクション 4.12.7.4 では、pow関数について次のように述べています。

シノプシス

#include <math.h>
double pow(double x, double y);
float powf(float x, float y);
long double powl(long double x, long double y);

説明

関数はを累乗してpow計算します。が有限かつ負であり、かつ有限で整数値でない場合、定義域エラーが発生します。範囲エラーが発生する場合があります。が 0 でが 0の場合、ドメイン エラーが発生する可能性があります。がゼロで、ゼロ未満の場合、定義域エラーまたは範囲エラーが発生する可能性があります。xyxyxyxy

戻り値

pow関数は [累乗x] をy返します。

関数の複雑さに関する情報は提供されておらず、使用されるアルゴリズムについては期待されていないことに注意してください。これは、関数が C の一部の実装ではプロセッサにネイティブである可能性があるためです。一方、他のアーキテクチャでは、浮動小数点処理はハードウェアによって提供されません。

ただし、複雑さはlog、乗算、およびexp組み合わせたものより悪くないと仮定できます。

double pow(double x, double y) {
    return exp(log(x)*y);
}

FP ユニットを備えた多くのプラットフォームでは、基数 e のべき乗、浮動小数点の乗算、および自然対数はすべてO(1)時間powがかかります。

exp-edit2-との複雑さについてはよくわかりませんが、log実装ではテイラー近似と一連のルックアップ テーブルを使用していると思います。それはまだ与えるでしょうO(1)。

于 2012-12-31T18:17:51.933 に答える
0

前の答えが言うように、言うことは不可能です。

fyl2xx86 では、 (y *log2(x)) を計算し、f2xm1命令 [+1.0 とともに]を使用して実装できます。

fld1            1.0
fld             y
fld             x 
fyl2x                  // y * log2(x)
fadd                   // add 1.0
f2xm1                  // 2 ^ (x-1)

次に、浮動小数点ユニットで exp/log 命令をまったくサポートしていない、またはほとんどサポートしていないプロセッサでは、log と exp はおそらく、入力値と方程式の良し悪しに応じて 5 ～ 20 回の反復を必要とする系列方程式を使用して計算されます。

その場合でも O(1) の複雑さは考慮されると思いますが、そのように機能しないシナリオを考え出すことができると確信しています。

于 2012-12-31T20:08:22.533 に答える