在这种情况下，合适的算法时间复杂度方程是什么？
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)
最佳答案
复杂度为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) 快吗？仅当我们拥有超过一百万个对象时，情况才会如此。
希望这对您有所帮助!
关于algorithm - 这里的时间复杂度是多少？ O(NlogN) 还是 O(logN^2)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52936493/