我想有一个清单

listA=[679,890,907,780,5230,781]


并想要删除另一个中存在的某些元素

listB=[907,5230]


以最小的时间复杂度?

我可以通过使用两个“ for循环”来解决这个问题,即O(n2)的时间复杂度,但是我想将此复杂度降低为O(nlog(n))或O(n)?
可能吗?

最佳答案

有可能-如果列表之一已排序。假设列表A已排序且列表B未排序,且维度分别为MN,则从列表A中删除所有列表B元素的最小时间复杂度将为O((N+M)*log(M))。实现此目的的方法是通过二进制搜索-列表A中元素的每次查找都花费O(log(M))时间,并且存在N查找(列表B中每个元素都查找一次)。由于对A排序需要花费O(M*log(M))的时间,因此对大型列表进行排序然后删除所有元素的效率更高,总时间复杂度为O((N+M)*log(M))

另一方面,如果没有排序列表,请使用Collection.removeAll,在这种情况下,其时间复杂度为O(M*N)。这种时间复杂性的原因是removeAll在默认情况下会执行以下伪代码:

public boolean removeAll(Collection<?> other)
    for each elem in this list
        if other contains elem
            remove elem from this list


由于contains对于列表的时间复杂度为O(N),而您最终要进行M迭代,因此总共要花费O(M*N)的时间。

最后,如果您想最小化removeAll的时间复杂度(可能会降低现实世界的性能),则可以执行以下操作:

List<Integer> a = ...
List<Integer> b = ...
HashSet<Integer> lookup = new HashSet<>(b);
a.removeAll(lookup);


对于错误的b值,构造lookup的时间可能要花费时间O(N*log(N)),如here所示(请参阅“病理分布的键”)。此后,调用removeAll将在O(1)迭代中将contains用于M,需要花费O(M)的时间执行。因此,此方法的时间复杂度为O(M + N*log(N))

因此,这里有三种方法。一个为您提供时间复杂度O((N+M)*log(M)),另一个为您提供时间复杂度O(M*N),最后一个为您提供时间复杂度O(M + N*log(N))。考虑到第一个和最后一个方法在时间复杂度上是相似的(因为log甚至对于大量数字来说都非常小),我建议对于小输入使用朴素的O(M*N),对于中等输入使用最简单的O(M + N*log(N))大小的输入。从创建HashSet来存储B元素(非常大的输入)开始,您的内存使用开始受到困扰,我最终将切换到更复杂的O((N+M)*log(M))方法。

您可以找到AbstractCollection.removeAll实现here

编辑:
第一种方法不适用于ArrayLists-从列表A的中间删除显然需要O(M)时间。而是对列表B(O(N*log(N)))排序,并遍历列表A,并根据需要删除项目。这花费了O((M+N)*log(N))的时间,并且比使用ArrayList时得到的O(M*N*log(M))更好。不幸的是,此算法的“适当删除项目”部分要求您创建数据以将未删除的元素存储在O(M)中,因为您无权访问列表A的内部数据数组。在这种情况下,最好使用HashSet方法。这是因为(1)O((M+N)*log(N))的时间复杂度实际上比HashSet方法的时间复杂度差,并且(2)新算法没有节省内存。因此,只有在您的列表具有O(1)的删除时间(例如LinkedList)和大量数据时,才使用第一种方法。否则,请使用removeAll。它更简单,通常更快并且得到库设计人员的支持(例如ArrayList具有custom removeAll实现,允许它使用微不足道的额外内存占用线性时间而不是二次时间)。

09-10 08:25
查看更多