作者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