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

Question

我需要使用大 O 符号计算以下方程的计算复杂度：

这里，m是接入点总数（从复杂度上讲可能是迭代次数，i是个体接入点）。我了解了 Big-O 符号形式 this blog. Moreover, I found a similar question at this link。在上面的等式中，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）。我的问题类似于两个未嵌套且具有不同迭代的循环 N>>m。

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

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

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

Answer 1

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

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

有什么关系

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

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

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

Computational complexity (Big-O notation) of a geometrical weighted centroid among access points

algorithm

complexity-theory

big-o

time-complexity