Re: [問題] 在O(|V|)的時間內找到non-cut點
看板Prob_Solve (計算數學 Problem Solving)作者fenzhang (分帳)時間11年前 (2013/08/03 17:20)推噓2(2推 0噓 8→)留言10則, 3人參與討論串7/7 (看更多)
我的意思是你所說的第一點
題目叫我們O(V)的時間找NON-CUT點
沒有要我們考慮輸入時間吧
你可以說O(V)的演算法不存在所以題目敘述錯誤
但不能說輸入要O(V+E)就是題目不夠嚴謹
就我舉的例子來說，沒有錯，輸入完整張圖的確是要O(V+E)
但是如果每加一個點就詢問一次而且真的有O(V)的演算法可以回答這個問題
這樣總複雜度就是O(V^2+E)
我舉這個例子只是想反駁你"輸入時間比算法時間長等同於題目不夠嚴謹"這個敘述
給你一張無向圖，請設計一個O(V)的演算法找一個NON-CUT點
給你一個有序數列，請設計一個O(lgN)的演算法找序列中有多少數小於K
我個人的想法是
如果看到下面那題應該不能說輸入序列就要O(N)所以題目不嚴謹
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.137.76
推
08/03 19:48, , 1F
08/03 19:48, 1F
→
08/03 19:53, , 2F
08/03 19:53, 2F
→
08/03 19:55, , 3F
08/03 19:55, 3F
→
08/03 19:56, , 4F
08/03 19:56, 4F
→
08/03 19:58, , 5F
08/03 19:58, 5F
推
08/06 20:42, , 6F
08/06 20:42, 6F
→
08/06 20:43, , 7F
08/06 20:43, 7F
→
08/06 20:43, , 8F
08/06 20:43, 8F
→
08/06 20:51, , 9F
08/06 20:51, 9F
→
08/06 20:52, , 10F
08/06 20:52, 10F
討論串 (同標題文章)
完整討論串 (本文為第 7 之 7 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
