作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 面试问到的问题...
时间Thu Dec 13 14:07:53 2012
※ 引述《Favonia (小西风最乖了*^^*)》之铭言：
: 总而言之，如果我上个段落後半部没有想错的话，先考
: 虑所有垂直线，然後通过对偶在参数平面上用 Bentley-
: Ottmann 找交点。全部应该可以在 O(nlgn) 时间内完成。
Bentley-Ottmann 的时间复杂度其实是 O((n+k)*lgn)，其中 k 是交点个数。
经过对偶之後，这些直线最多出现 C(n,2) = O(nn) 个交点。
完成的时间最差是 O(nnlgn) 而不是 O(nlgn)。
事实上还有比 Bentley-Ottmann 更好的演算法：
http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf
理论上可以做到 O(nlgn + k)，在本题中也就是 O(nn)。
只是这个演算法不太容易实作，反倒是原po提出的 hashing 还比较务实。
－
接着说明一下直线截成线段的问题。
对偶的时候，点(a,b)对偶成直线y=ax+b。
考虑两个直线的交点，也就是两条直线解联立方程式。
根据公式解(Cramer's rule)，
ax+by=e, cx+dy=f 这两条直线，
其交点的x座标范围一定会在 |e|*|d|+|b|*|f| 之内（当abcdef都是整数）。
所以我们只要设立一个足够大与一个足够小的x座标，再把x座标代入到直线中求得y座标，
就可以把直线截成线段，同时保留所有直线交点。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 36.225.135.22
※ 编辑: DJWS 来自: 36.225.135.22 (12/13 16:04)
※ 编辑: DJWS 来自: 36.225.135.22 (12/13 16:05)
※ 编辑: DJWS 来自: 36.225.135.22 (12/13 16:16)
1F：推 Favonia:啊我记错复杂度了 orz 12/13 19:12
2F：推 Favonia:理论上的进展是，很多 O(1) hash 都是随机 hash 12/13 19:17
3F：→ Favonia:如果找线段不是随机的，那就有个 O(n^2) 不随机的演算法 12/13 19:17
4F：→ DJWS:想请问一下随机和不随机是什麽意思? 12/13 21:45