列表比较算法复杂度的改进
我有两个数组array1 = Array<List<Integer>>和array2 = Array<Integer>，我遍历array2。然后，我尝试从array1列表中查找array2中的当前项可能在哪个列表中。我从array1检索相应的列表，并遍历它，看看是否能在array1中找到类似的数字。我将相似度定义为在某些错误ε内相等的数字(即，由于7-6=1，6将被发现等于具有7的epsilon=1 )。如果数字相等，我将它们添加到一个名为matchList的列表中。最后，我有一个名为resultList的matchList列表。
下面是一些伪代码：
List<List<Integer>> resultList = new ArrayList<List<Integer>>();
for (i = 0; i < array2.length; i++) {
int index = array2[i] % n;
List<Integer> currentList = array1[index];
List<Integer> matchList = new LinkedList<Integer>();
while(int currentItem : currentList) {
if (currentItem - array2[i] < epsilon){
matchList.add(currentItem);
}
}
if (!matchList.isEmpty()){
resultList.add(matchList);
}
}我的问题是，我是否可以改善这个O(n*m)算法的复杂性。我已经通过预分配数组、使用迭代器遍历链表、使用原语类型集合(Trove而不是Java的内置)和其他一些措施，极大地提高了算法的速度。
编辑:我只对改善big-O运行时的建议感兴趣。
回答 1
Stack Overflow用户
发布于 2014-08-13 05:15:15
为了在算法上解决这个问题(简单地按照评论中的建议并行运行你的算法并不会降低你的算法复杂度)，你需要引入一个更有效的数据结构，它允许你执行更快的查找。
您将首先创建存储桶，其中每个存储桶包含给定范围(value加/减epsilon)中的值。因此，一个列表值可以在多个存储桶中。您至少可以在O(n * #buckets)中创建此遗愿列表，可能会更少，这取决于您是否对值的分布有一个假设。
接下来，您可以根据这些存储桶检查您的其他列表。根据范围的比率和这些存储桶的值的数量，懒惰地创建存储桶并在某种哈希表中组织存储桶本身可能是有效的。然后，您将遍历另一个列表，并检查存储桶中包含的值，这可以在O(m)时间内完成。
这样您就可以完全使用O(n * #buckets + m)了。
https://stackoverflow.com/questions/25273903
复制相似问题
腾讯云开发者
