如何用Math.pow或Math.log描述方法的Big O表示法

本文关键字：Math Big 表示 log 何用 pow 描述方法 | 更新日期: 2023-09-27 18:26:31

假设我的方法有一个pow/log的变量和一个常量：

double LogX(int x){
   return Math.Log(x, constantBase);
}
double PowX(int x){
   return Math.Pow(constant, x);
}

我不确定在使用数学函数时，这些函数的正确时间复杂度是多少。我的概念印象是，PowX将是O（n），因为它必须将常数乘以n-1倍，但我知道还有其他方法可以实现幂函数，但我找不到一个明确的答案来说明我应该在那里假设什么。如果它是常数时间，那么它是O（n）吗？我同样不确定如何正确地接近LogX。

如果这很重要的话，我会使用C#，但我希望对此有一个大致的理解。如果我只是有一个方程f=常数^x或f=log（x），那么对于这些时间复杂性，我会得到与通过数学函数不同的答案吗？

如何用Math.pow或Math.log描述方法的Big O表示法

对于具有有限位性的数字（如float/double/int），您可以将这些函数（以及其他函数，如sin/cos）视为O（1），因为当它们由浮点处理器执行时，它们有很好的定义边界，并且即使手动实现，用于计算函数的序列也可以用固定数量的元素来限制。

对于任意长的数字，您必须使用更复杂的估计，这也必须与您的实现直接相关。

即，像bigNumber^n（其中n是整数）这样的整数幂可以在O（log n）次乘法（样本）中计算，每次乘法的复杂性依次取决于每个数字中的位数（对于单次乘法O（initial_length_in_bits^2），对于所有乘法，我猜是^3）。因此，由此产生的复杂性将类似于O（logn*initial_length_in_bits^3）。

相关文章：