[Coursera] Standford Algorithm Design & Analysis II

bmbdl 发表于 2012-12-25 19:43
应该是O(301*n) = O(n)

我觉得两层嵌套for循环的确是O（304N），然后但是考虑到cluster的update，每个节点最多update log（n） 次，n个节点最多update nlog（n）次

那 O（nlogn）> O（304n），整体取O（nlogn）

writecoffee1 发表于 2012-12-26 15:00
我觉得两层嵌套for循环的确是O（304N），然后但是考虑到cluster的update，每个节点最多update log（n） 次 ...

find-union在union的时候并不需要更新所有的节点。

这个复杂度分析确实比较那啥，我就不纠结了。。CLRS上disjoint-set那一章没看过，搞不清。。

稍微改进了下，12s了。ruby也不比C++什么的慢呀，哈哈。

前边盖了这么多楼，LZ或哪位同学给week 3单开个帖吧~

bmbdl 发表于 2012-12-26 08:16
稍微改进了下，12s了。ruby也不比C++什么的慢呀，哈哈。

前边盖了这么多楼，LZ或哪位同学给week 3单开个 ...

非常抱歉，圣诞出去玩了，编程作业还是在宾馆做的，就没顾上更新帖子。