我想知道在 c++ 中构建的 pow() 函数的最坏情况下的时间复杂度是多少？
问问题
21771 次
3 回答
17
这取决于底层架构。在最常见的桌面架构 x86 上，这是一个恒定时间操作。
有关如何在 x86 上实现它的更多详细信息，请参阅此问题：How to: pow(real, real) in x86
于 2012-11-16T14:10:11.403 回答
2
这是一个实现，看看。可以肯定的是，这是一段相当复杂的代码，有 19 种特殊情况。时间复杂度似乎不依赖于传入的值。
以下是用于计算 的方法的简短描述pow(x,y)：
Method: Let `x = 2 * (1+f)`
计算并分两部分返回
log2(x)：log2(x) = w1 + w2，其中w1有53-24 = 29位尾随零。
y*log2(x) = n+y'通过模拟多精度算术来执行，其中|y'|<=0.5.返回
x**y = 2**n*exp(y'*log2)
于 2012-11-16T14:10:46.727 回答
1
你没有提到你使用的是什么系统/架构，所以我们只能猜测。
但是，如果您不是在寻找细节而只想浏览免费提供的实现代码，请参见 http://www.netlib.org/fdlibm/，特别是http://www.netlib.org/fdlibm/w_pow 。C
有关更多背景信息，请参阅此问题的答案：https ://stackoverflow.com/a/2285277/25882
于 2012-11-16T14:21:59.517 回答