c# - 如何使用 Math.pow 或 Math.log 描述方法的大 O 表示法？

Question

假设我的方法有一个变量和一个用于 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=constant^x 或 f=log(x)，对于这些时间复杂度，我会得到与通过数学函数得到的不同的答案吗？

Answer 1

对于位数有限的数字(如 float/double/int)，您可以考虑这些函数(连同其他一次像 sin/cos) 一样 O(1) 因为当它们被浮点处理器执行时，它们有明确定义的界限，即使手动实现用于计算的系列可以使用固定数量的元素来限制功能。

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

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