[其他] 互斥規則

看板Math作者 (.....)時間12年前 (2013/07/30 09:31), 編輯推噓1(1推 0噓 2→)
留言3則, 1人參與, 最新討論串1/2 (看更多)
假設A群有 [a1,a2,a3,a4,a5] 個元素 B群有 [b1,b2,b3,b4] 個元素 若已知 an 與 bn 互斥關係表 (ex:定義 a2與b3互斥、a5與b4互斥) 一般來說要找A群與B群之間的元素是不是存在互斥關係 大概都是從 a1->b1,b2,b3,b4 a2->b1,b2,b3,b4 a3->b1,b2,b3,b4 a4->b1,b2,b3,b4 a5->b1,b2,b3,b4 這樣一個一個去比較是不是有互斥 (O(n^2)) 有什麼比較快的演算法可以很快知道 A群和B群之間是不是有互斥的關係存在? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.71.217.244
推
07/30 10:34, , 1F
互斥關係是怎麼給的? 如果是一個個 pair, 那麼你的
07/30 10:34, 1F
→
07/30 10:34, , 2F
演算法與表的大小會一樣, 最糟的情形就是全部要檢查.
07/30 10:34, 2F
→
07/30 10:35, , 3F
除非互斥關係有什麼結構?
07/30 10:35, 3F
‣ 更多 luoqr 的文章
文章代碼(AID): #1HznUAv4 (Math)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
其他
1
3
[其他] 互斥規則 互斥規則
luoqr
12年前, 07/30
在新視窗開啟完整討論串 (共2篇)
‣ 更多 luoqr 的文章
文章代碼(AID): #1HznUAv4 (Math)