c# - 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)：

换句话说，Math.Sqrt() 转换为单个浮点机器代码指令

来源： c# Math.Sqrt 实现

Answer 2

正如 BlackBear 所提到的， Math.Sqrt实现转换为单个浮点机器代码指令 (fsqrt)。该指令的周期数是有限的（这里有一些示例）。这意味着它的复杂度是 O(1)。

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

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