algorithm - 这里的时间复杂度是多少？ O(NlogN) 还是 O(logN^2)？

Question

在这种情况下，合适的算法时间复杂度方程是什么？

A : O(NlogN)

B : O(logN^2)

其中 N 是对象(边界体积)的数量，记录 交叉迭代(光线反弹多少次)。

Set Camera Position (eye position) 

IF (Object – is found in the scene) 
|  Create Bounding Volume (BV)

For (ALL BV)
|  Get Min-Max Values for X,Y Coordinates 
|  Eliminate Intersection Testings 
|  IF (2 or more Objects are close in range)  
|  |  Intersect(Ray, Object(s)) 
|  |  FOR (each Triangle (T) in the object) 
|  |  |  Intersect(Ray, T) 
|  |  |  E.g Detect Colour And Texture
|  ELSE (Do not Intersect) 

Answer 1

复杂度为O(NlogN)。

这是因为:

<强>1。有一个外层 for 循环 :有了这个外层 for 循环，你的时间复杂度已经是 O(N)。

这部分可能有点困惑。我们将考虑两种情况。

最坏情况:每个循环都有 2 个或更多对象接近范围。

这使得算法复杂度为 O(N^2)，因为现在您需要在每次迭代中都执行内部 for 循环!!!但是，您的 if 语句不太可能始终为真...因此我们还需要处理最佳情况。

最佳情况:没有物体在范围内很近。

这使得算法复杂度为 O(N)，因为您不必再​​进入内部 for 循环!我们只会检查 if 语句并继续下一次迭代。

那么时间复杂度是多少呢？ O(N^2) 或 O(N)？

现在我们讨论分摊运行时间。摊销运行时间只是意味着同时考虑最坏情况和最好情况(有关摊销分析的更多信息，请参见此处:https://en.wikipedia.org/wiki/Amortized_analysis)。

所以我们同时考虑 O(N^2) 和 O(N)。假设我们运行 if 语句的时间有一半(摊销)，时间复杂度将为 O(NlogN)。

O(NlogN) 比 O(N) 快吗？仅当我们拥有超过一百万个对象时，情况才会如此。

希望这对您有所帮助!