Re: [問題] 在O(|V|)的時間內找到non-cut點

作者: fenzhang (分帳)   2013-08-03 17:20:51
我的意思是你所說的第一點
題目叫我們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)所以題目不嚴謹
作者: DJWS (...)   2013-08-03 19:48:00
瞭解了! 多謝你的解釋如果有序數列儲存在stack裡面,它會有O(lgN)的演算法嗎?我想說的是這樣:如果時間複雜度要低於輸入大小,那麼就要對輸入格式進行假設。不過這道題目並沒有提到這件事。想要深入了解的板友,可以搜尋一下sub-linear time algorithm
作者: magrady (元元)   2013-08-06 20:42:00
很有道理, 時間複雜度要低於輸入大小的話, 通常就沒有辦法隨心所欲的轉換資料成為方便處裡的資料結構所以我覺得明確的定義輸入後使用的資料是必須的
作者: bleed1979 (十三)   2013-08-06 20:51:00
一般演算法課本的虛擬碼都不太管輸入的。傳入一個array就假設裡面已經有值。

Links booklink

Contact Us: admin [ a t ] ucptt.com