我想有一个清单
listA=[679,890,907,780,5230,781]
并想要删除另一个中存在的某些元素
listB=[907,5230]
以最小的时间复杂度?
我可以通过使用两个“ for循环”来解决这个问题,即O(n2)的时间复杂度,但是我想将此复杂度降低为O(nlog(n))或O(n)?
可能吗?
最佳答案
有可能-如果列表之一已排序。假设列表A已排序且列表B未排序,且维度分别为M
和N
,则从列表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
实现,允许它使用微不足道的额外内存占用线性时间而不是二次时间)。