Какая здесь сложность времени?O (NlogN) или O (logN ^ 2)? - PullRequest
Новая
       64

Какая здесь сложность времени?O (NlogN) или O (logN ^ 2)?

0 голосов
/ 22 октября 2018

Каков алгоритм соответствующего уравнения сложности времени в этом случае?

A: O (NlogN) * ​​1003 *

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)

1 Ответ

0 голосов
/ 22 октября 2018

Сложность: O (NlogN) * ​​1002 *.

Это потому что:

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)? Это будет толькоtrue, если у нас более миллиона объектов.

Надеюсь, это поможет!

...