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

Question

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

这里，m是接入点的总数(从复杂度上讲可能是迭代次数，i是个体接入点)。我了解了 Big-O 符号形式 this博客。此外，我在 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 符号而言，最终的计算复杂度是多少？

谢谢。

更新:

带有x 和y 的下标w 只是一种符号。这不是迭代。迭代只有 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) 时间。所有其他操作都是不变的，您没有任何 sub-sum in sum 或类似的东西。

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

---

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

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