#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; }
这里使用什么算法来查找 an。这个 pow() 函数的复杂度是多少?。
最佳答案
C99 标准的第 4.12.7.4 节除了以下内容外,没有更多关于 pow
函数的内容:
Synopsys
#include <math.h> double pow(double x, double y); float powf(float x, float y); long double powl(long double x, long double y);
Description
The
pow
functions computex
raised to the powery
. A domain error occurs ifx
is finite and negative andy
is finite and not an integer value. A range error may occur. A domain error may occur ifx
is zero andy
is zero. A domain error or range error may occur ifx
is zero andy
is less than zero.Returns
The
pow
functions return [x
raised to the powery
].
请注意,没有给出有关函数复杂性的信息,并且对要使用的算法没有期望。这是因为在某些 C 实现中,这些函数可能是处理器 native 的,而在其他体系结构上,浮点处理不是由硬件提供的。
不过,您可以假设复杂性并不比 log
、乘法和 exp
的组合差:
double pow(double x, double y) {
return exp(log(x)*y);
}
在许多具有 FP 单元的平台上,以 e 为底的求幂、浮点乘法和自然对数都需要 O(1)
时间,因此 pow
也应该如此.
-edit2- 我不太确定 exp
和 log
的复杂性,但我认为实现使用泰勒近似和一堆查找表。这仍然会给出 O(1)
。
关于c - c中的pow()函数使用什么算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14104711/