数学的时间复杂性.Sqrt()

本文关键字：Sqrt 时间复杂性 | 更新日期: 2023-09-27 18:28:45

如何查找此函数的复杂性？

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()的复杂度是多少。

数学的时间复杂性.Sqrt()

正如BlackBear所提到的，Math.Sqrt实现将a转换为单浮点机器代码指令（fsqrt）。此指令的循环数是有界的（以下是一些示例）。这意味着它的复杂性是O（1）。

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

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

您可以将其视为O（1）:

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

来源：c#Math.Sqrt实现

相关文章：