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

[fenzhang (分帳)]

我的意思是你所說的第一點

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