这里的时间复杂度是多少? O(NlogN) 还是 O(logN^2)?
What is the time complexity here ? O(NlogN) or O(logN^2)?
在这种情况下,算法的适当时间复杂度方程是什么?
A : O(NlogN)
B : O(logN^2)
其中 N 是对象(边界体积)的数量,log 是交叉迭代(光线反弹多少次) .
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 语句不太可能始终为真...因此我们还需要注意 最佳情况。
最佳情况:None 个对象在范围内。
这使得算法复杂度为 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) 快吗?仅当我们拥有超过一百万个对象时才会如此。
希望对您有所帮助!
在这种情况下,算法的适当时间复杂度方程是什么?
A : O(NlogN)
B : O(logN^2)
其中 N 是对象(边界体积)的数量,log 是交叉迭代(光线反弹多少次) .
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 语句不太可能始终为真...因此我们还需要注意 最佳情况。
最佳情况:None 个对象在范围内。
这使得算法复杂度为 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) 快吗?仅当我们拥有超过一百万个对象时才会如此。
希望对您有所帮助!