作者fenzhang (分帳)
站內Prob_Solve
標題Re: [問題] 在O(|V|)的時間內找到non-cut點
時間Sat Aug 3 17:20:51 2013
我的意思是你所說的第一點
題目叫我們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
1F：推 DJWS:瞭解了! 多謝你的解釋 08/03 19:48
2F：→ DJWS:如果有序數列儲存在stack裡面，它會有O(lgN)的演算法嗎？ 08/03 19:53
3F：→ DJWS:我想說的是這樣：如果時間複雜度要低於輸入大小，那麼就要對 08/03 19:55
4F：→ DJWS:輸入格式進行假設。不過這道題目並沒有提到這件事。 08/03 19:56
5F：→ DJWS:想要深入了解的板友，可以搜尋一下sub-linear time algorithm 08/03 19:58
6F：推 magrady:很有道理, 時間複雜度要低於輸入大小的話, 通常就沒 08/06 20:42
7F：→ magrady:有辦法隨心所欲的轉換資料成為方便處裡的資料結構 08/06 20:43
8F：→ magrady:所以我覺得明確的定義輸入後使用的資料是必須的 08/06 20:43
9F：→ bleed1979:一般演算法課本的虛擬碼都不太管輸入的。 08/06 20:51
10F：→ bleed1979:傳入一個array就假設裡面已經有值。 08/06 20:52