我有两套 Animal
物体。动物之间的距离是用一种特定的算法来定义的,这种算法可以观察动物的特征。我正在尝试设计一种方法,从两个集合(每个集合一个)中找到一对,从而使距离最小化。
我有一个想法:创建一个参数化的 Tuple
要配对的类 Animals
. 创建 PriorityQueue
用比较器排序 Tuple<Animal>
根据两个成员之间的距离。然后,从中选出第一对 PriorityQueue
.
这是好的设计,还是浪费?我相信它会在o(m+n)时间内运行,其中m和n是每个集合的大小。
如果 Tuple
是一个参数化的类,在它上面使用一个只在 Animal
?
我想用这个 findMinimalPair
一种生成树的方法,该生成树最小化图的距离 Animal
物体。如果我不停地把一对一对地弹下来呢 PriorityQueue
,检查以确保每对仍包含每个集合的一个成员?
这是一个基本的例子。以下是距离:
A0 A1 A2 A3
A0 0 20 33 8
A1 20 0 102 73
A2 33 102 0 6
A3 8 73 6 99
假设集合是:
a0级
a1、a2、a3
下面是元组的排序顺序,按距离:
(A0, A3) - 8
(A0, A1) - 20
(A0, A2) - 33
所以我们看到a3是最接近的。a3随后被移入第一个集合:
a0、a3级
a1、a2
再次检查最小对:
(A3, A2) - 6
(A0, A1) - 20
(A0, A2) - 33
(A3, A1) - 73
现在a2被拿走了。看看它是怎么工作的?
这就是我最后要做的。评论?
3条答案
按热度按时间t2a7ltrp1#
实际上,为了得到所有可能的元组,需要创建mn元组,这需要o(mn)。您需要对元组列表进行排序,这些元组的最小值为o(mnlog(mn)),因此复杂性为o(mnlog(mn))——即使使用优先级队列(您将有mn个插入,每个插入都有o(log(mn))复杂性)。
编辑
刚才在上面的解决方案中看到一个错误-如果您只想找到最小的对,那么实际的复杂性是o(mn),因为您需要所有对上的一条路径。如果你想有一个按距离排序的所有对的列表,以便得到最小生成树,那么它就是o(mnlog(mn))。在任何情况下,它都不是o(m+n)
2nc8po8w2#
我的建议是使用元组,元组会给出o(n.m)(而不是o(n+m))。然后使用bucket sort算法bucket sort,其中每个bucket都是一个元组。。所以你会得到o(n.m)对你的问题(根据我对你的问题的理解,你可以使用bucket sort,否则你将不得不使用o(nlogn)算法)
unguejic3#
如果你想找出集合1和集合2之间所有可能的元组之间的距离,我认为你可能会被嵌套循环所困扰,结果是o(m*n)。我不认为有任何方法可以得到o(m+n)。
如果我没记错的话,在找到最小生成树之前,需要一个完整的图。看起来这个图有o(v^2)条边(因为每对动物之间都有一段距离),所以如果你使用prim的算法来寻找最小生成树,你可能需要使用fibonacci堆和邻接列表(即o(e+v log(v)))。
http://en.wikipedia.org/wiki/prim%27s_algorithm