我的意思是你所說的第一點
題目叫我們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)所以題目不嚴謹