如何使用 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)，因为当它们由浮点处理器执行时，它们有明确定义的界限，即使手动实现用于计算函数的系列也可以限制为固定数量的元素。

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

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

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

How do I describe the Big O notation of a method with Math.pow or Math.log?

c#

big-o

time-complexity