Re: [問題] 面試問到的問題...
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間12年前 (2012/12/13 15:34)推噓1(1推 0噓 4→)留言5則, 2人參與討論串7/8 (看更多)
※ 引述《DJWS (...)》之銘言：
: ※ 引述《Favonia (小西風最乖了*^^*)》之銘言：
: : 總而言之，如果我上個段落後半部沒有想錯的話，先考
: : 慮所有垂直線，然後通過對偶在參數平面上用 Bentley-
: : Ottmann 找交點。全部應該可以在 O(nlgn) 時間內完成。
: Bentley-Ottmann 的時間複雜度其實是 O((n+k)*logn)，其中 k 是交點個數。
: 經過對偶之後，這些直線最多出現 C(n,2) = O(n^2) 個交點。
: 完成的時間最差是 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。
: 考慮兩個直線的交點，也就是兩條直線解聯立方程式。
: 根據公式解，交點的座標範圍一定會在 |a|*|b|+|c|*|d| 之內。
First, I don't understant your notation.
What do you mean by the range |a|*|b|+|c|*|d| ?
It seems not a range in 2D ?
And I have the same question for you.
Assume you have N lines, based on your description
You claim there is a range for the intersection.
Then, how many operations you need to calculate the range?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 142.136.127.136
推
12/13 15:39, , 1F
12/13 15:39, 1F
→
12/13 15:40, , 2F
12/13 15:40, 2F
→
12/13 15:41, , 3F
12/13 15:41, 3F
→
12/13 15:43, , 4F
12/13 15:43, 4F
→
12/19 12:11, , 5F
12/19 12:11, 5F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 7 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
