Math.Sqrt() 的时间复杂度？

Question

如何找到这个函数的复杂度？

private double EuclideanDistance(MFCC.MFCCFrame vec1, MFCC.MFCCFrame vec2)
{
  double Distance = 0.0;
  for (int K = 0; K < 13; K++)
     Distance += (vec1.Features[K] - vec2.Features[K]) * (vec1.Features[K] - vec2.Features[K]);
  return Math.Sqrt(Distance);
}

我知道下面的部分是 O(1):

double Distance = 0.0;
for (int K = 0; K < 13; K++)
   Distance += (vec1.Features[K]-vec2.Features[K])*(vec1.Features[K]-vec2.Features[K]);

但是我搞不懂Math.Sqrt()的复杂度是多少

Answer 1

可以考虑O(1):

In other words, Math.Sqrt() translates to a single floating point machine code instruction

来源： c# Math.Sqrt Implementation

Answer 2

正如 , the Math.Sqrt implementation translates to a to a single floating point machine code instruction (fsqrt). The number of cycles of this instruction is bounded (here 提到的一些例子）。这意味着它的复杂度是 O(1).

确实如此，因为我们使用的浮点值数量有限。该操作的“实际”复杂性取决于输入的位数。 Here你可以找到一个基本算术函数的复杂度列表。根据该列表，平方根函数具有乘法函数的复杂性（两个 n 位数的 O(n log n)）。

你说，你假设加法和乘法函数的复杂度为 O(1)。这意味着，您可以假设平方根函数虽然慢得多，但复杂度也为 O(1)。

Math.Sqrt() 的时间复杂度？

Time complexity of Math.Sqrt()?

c#

big-o

time-complexity

math.sqrt