时间戳

首页 > 解决方案 > 接入点之间几何加权质心的计算复杂度（Big-O 表示法）

algorithm - 接入点之间几何加权质心的计算复杂度（Big-O 表示法）

问题描述

我需要使用 Big-O 表示法计算以下方程的计算复杂度：

在此处输入图像描述

这里，m是访问点的总数（也许就复杂性而言，迭代次数i是单个访问点）。我从这个博客中了解了 Big-O 表示法。此外，我在这个链接上发现了一个类似的问题。在上面的等式中，d是用 4 次运算（乘法、减法、除法和幂）计算的距离。如上式所示，w用两个操作（幂和除法）计算。xw并且yw分别用两个运算（乘法和除法）计算。因此，我将上述算法的 Big-O 表示法计算为：

4*[m]+2*[m]+2*[m]+2*[m]

这是对的吗？可以近似为O(m)? 此外，上述算法（方程）与计算复杂度为 的下一个算法相结合，O(N)即N迭代次数。在这里，N>>m。就 Big-O 表示法而言，最终的计算复杂度是多少？

谢谢你。

更新：

w带有x和的下标y只是一个符号。这不是迭代。迭代只是m. 例如。i = 1,2,3,4,5,......,m.这两种算法以流水线方式运行。例如，首先m运行具有迭代的算法，并将该算法的输出（作为输入）馈送到具有N迭代的下一个算法。因此，当m迭代（算法 1）完成时，接下来是N迭代（算法 2）。我的问题类似于两个未嵌套且具有不同迭代的循环 where N>>m.

for(int i=0; i<m; i++){
   System.out.println(i);
}

for(int j=0; j<N; j++){
   System.out.println(j);
}

最终的计算复杂度是多少？

标签： algorithmtime-complexitybig-ocomplexity-theory

解决方案

i=1是的，您从到的总和i=m需要O(m)时间。所有其他操作都是不变的，你没有任何总和或类似的东西。

关于您的N价值，您没有提供足够的信息。我们必须知道N是如何计算的或者它是如何与 相关的m。

此外，您应该考虑以下约束 - 您能否提供一些数字或方程式永远无法达到的最大值（甚至难以置信）？通常对数字的操作被认为是常数，因为它们是在 32 或 64 位数字上进行的，这些数字总是需要常数时间。

但是，如果您有一些方程式具有令人难以置信的长数字（例如数百个字符长或更多），则必须考虑数字的大小的复杂性。（您可能可以想象，将两个数以百万计的字符相乘比用 2x2 做同样的操作需要更多的时间）

推荐阅读