Re: [問題] 在O(|V|)的時間內找到non-cut點
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間11年前 (2013/08/02 09:21)推噓1(1推 0噓 5→)留言6則, 2人參與討論串6/7 (看更多)
→
07/31 22:52,
07/31 22:52
推
08/02 02:33,
08/02 02:33
僅僅讀取 vertex 的資訊
而不讀取 edge 的資訊
怎麼可能判斷連通？
既然一定得讀取 edge
時間複雜度就至少是 O(V+E) 等級的
那麼有沒有辦法不必讀取所有的 edge 呢？有的：
一、vertex和edge要事先處理，然後儲存於一個特別的資料結構。
就好比是 binary search，除非資料預先排序，不然不可能低於線性時間。
不過題目沒交代這件事，所以我們不能自行假設。
二、運用一些特別的數學性質，例如 degree = 0 or 1 的點一定是 non-cut vertex。
不過我從未聽過有什麼數學性質可以在O(V)解決這問題的。
這也已經脫離演算法的範疇了，
三、randomizd algortihm。
不過不能保證100%正確，應該不是這個題目想問的方向。
我只知道這些，可能還有什麼其他的策略。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
圖上每次增加一點就詢問一次
那麼圖上所有點和邊都增加完之後
最後還是 O(V+E) 呀
也許你的意思是均攤
但是均攤不是這樣用的
就好比說我要找兩點之間最短路徑
使用 floyd-warshall O(V^3)
圖上共有 C{V,2} = O(V^2) 個點對
所以，兩點之間最短路徑的「均攤時間複雜度」是 O(V)
但是這並不表示兩點之間最短路徑的「時間複雜度」是 O(V)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.133.106
※ 編輯: DJWS 來自: 36.225.133.106 (08/02 09:21)
推
08/02 10:38, , 1F
08/02 10:38, 1F
→
08/02 10:38, , 2F
08/02 10:38, 2F
→
08/02 10:40, , 3F
08/02 10:40, 3F
→
08/02 10:40, , 4F
08/02 10:40, 4F
→
08/02 10:40, , 5F
08/02 10:40, 5F
※ 編輯: DJWS 來自: 36.225.133.157 (08/03 10:13)
→
08/03 20:13, , 6F
08/03 20:13, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 7 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
