江苏龙网

  1. 首页 > 生活 > >

Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模

自己找到了一个关于这个空间规模的证明，所以就自己翻译并回答一下好了。这样其他有类似疑问的同学也可以参考参考。------------------------------------分割---------------------------------Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模

Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模

Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模

Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模

Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模

Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模

Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模
【Bentley Ottmann扫描线算法中，事件队列（event queue）的空间规模】

■网友
If the crossings found by the algorithm do not need to be stored once they have been found, the space used by the algorithm at any point in time is O(n): each of the n input line segments corresponds to at most one node of the binary search tree T, and as stated above the event queue contains at most 3nelements. This space bound is due to Brown (1981); the original version of the algorithm was slightly different (it did not remove crossing events from Qwhen some other event causes the two crossing segments to become non-adjacent) causing it to use more space.基本上我觉得这种问题应该先看wikipedia……


    推荐阅读


    上一篇：怎样看待男子为了给客户拍照爬火车顶导致触电身亡铁路的高压线有多危险

    下一篇：小CP手游商务是否应该尝试跳槽发行