我有一个正在为项目运行的代码。它是O(N ^ 2)，其中我的情况下N是200。有一种算法可以将此O(N ^ 2)转换为O(N logN)。这意味着，使用这种新算法，速度应该快100倍左右。但是，我只能得到2倍的增长(也就是快2倍)。
我正在尝试缩小范围，以查看是否弄乱了某些东西，或者这是否是我对该程序进行编码的固有方式。首先，我在嵌套类中有很多函数开销。例如，我有很多这样的东西(在很多循环中):
energy = globals->pair_style->LJ->energy();
由于我得到的实际数据是正确的结果，只是速度增加错误，我想知道函数开销实际上是否会导致速度降低多达50倍之多。
谢谢!
最佳答案
首先，您认为O(N logN)比O(N^2)的N=200快100倍左右，这是不正确的。 big-Oh表示法在上限中处理上限和行为，并且不考虑复杂性中的任何乘法常数。
其次，是的，由于管道中断，在现代硬件上，函数调用往往相对昂贵。为了弄清这对您有多大的影响，您必须提出一些微基准。