[Coursera] Standford Algorithm Design & Analysis II

moophis 发表于 2012-12-25 18:09
你的意思是每成功union一次减一吗？因为可能存在make union两个已经在一个cluster的节点的情况。

另外 ...

union之前要先find的。。。要不为什么叫find-union呢是吧

writecoffee1 发表于 2012-12-25 18:38
总时间复杂度可以认为是 O(301 * n log n) 不？

应该是O(301*n) = O(n)

moophis 发表于 2012-12-25 18:09
你的意思是每成功union一次减一吗？因为可能存在make union两个已经在一个cluster的节点的情况。

另外 ...

我写了的，在前边某楼，1+24+C(24,2)=301 ~= 300

bmbdl 发表于 2012-12-25 19:44
我写了的，在前边某楼，1+24+C(24,2)=301 ~= 300

我知道你的意思，但是文件里有重复的节点怎么办呢？就算知道有300种可能你怎么从所有节点里找有没有距离小于3的呢？我感觉还是要遍历一遍啊。。。。ps：我把find写在make union里了。。所以一直没说~~

moophis 发表于 2012-12-25 20:41
我知道你的意思，但是文件里有重复的节点怎么办呢？就算知道有300种可能你怎么从所有节点里找有没有距离小 ...

所有的节点已经放到find-union里了，对300种可能，每一个先find，如果能找到并且不在一个集合的话再union。

遍历节点是没有问题的，而且只遍历了一遍 (你起码把输入读一遍吧喂)，find-union的find效率是O(1)的。(由于节点是按整数处理的，所以无所谓用不用find-union了，用一个数组也行，就几万个元素。)

我们要避免的不是遍历节点，而是遍历边~

bmbdl 发表于 2012-12-25 23:07
所有的节点已经放到find-union里了，对300种可能，每一个先find，如果能找到并且不在一个集合的话再union ...

我感觉我好想确实是遍历边了。。。不过你说的这个还是有点不太明白。我还是先说一下我brute的方法吧你看看在哪优化吧：
1.读取数据（这个省不了）
2.把所有边扫一遍，把小于3的距离找出来，另存一下index
3.把全出来的merge
第二步迭代了O(N^2)次，不知道怎么优化了。

moophis 发表于 2012-12-25 23:29
我感觉我好想确实是遍历边了。。。不过你说的这个还是有点不太明白。我还是先说一下我brute的方法吧你看看 ...

嗯啊，就是第二步按照那300个来~ 用暴力的办法相当于每个节点都考虑了20k个配对节点(当然，平均是20k/2)。而实际上只有300个是可能的。所以。。

bmbdl 发表于 2012-12-25 23:36
嗯啊，就是第二步按照那300个来~ 用暴力的办法相当于每个节点都考虑了20k个配对节点(当然，平均是20k/2)。 ...

我原来一直不明白怎么找到那三百种可能。现在想想好像有思路了，不知道你是怎么实现的。我想的是在读数据的时候构造一个hash table，索引是24位hamming距离的全排列。然后在第二步的时候先计算出那300种需要的距离可能，然后分别在hash table中找，查找hash table的时间复杂度好像就可以是O(1)了。不过好像找300种排列的函数不太好写，而且其实也挺花时间的吧，虽然是常数级的时间复杂度。

moophis 发表于 2012-12-26 08:33
我原来一直不明白怎么找到那三百种可能。现在想想好像有思路了，不知道你是怎么实现的。我想的是在读数据 ...

前边某楼讲了，用的是ruby/python自带的permutation。

没有这个函数的话得自己实现个，搜全排列算法，代码挺短的，尤其是这里只是24个元素，不用考虑太复杂。

这个全排列其实是24个元素中分别有0，1，2个位置一，其余置零，表示哪些位需要改变，以得到需要的汉明距离。所以得到全排列后，还得把原来的节点label修改，得到新的label。然后就可以find再union了。

bmbdl 发表于 2012-12-26 09:35
前边某楼讲了，用的是ruby/python自带的permutation。

没有这个函数的话得自己实现个，搜全排列算法， ...

嗯，我再试试~谢谢了