如何降低 O(n^3) 的复杂度？

Question

我正在编写这个方法来查找 3 个数组中常见数字的数量（允许重复，例如，if A=[1,3,3,3,6], B=[3,3,1,5], C=[3,3,1,5,2]则方法应返回 3；两个 3 + 一个 1）。我用了3个for循环，但我觉得应该有更好的方法来做到这一点。这是我的代码：private static int common(int[] A, int[] B, int[] C){    int c=0;    List<Integer> visitedBs=new ArrayList<Integer>(), visitedCs=new ArrayList<Integer>();    for (int i = 0; i < A.length; i++)        outerloop:        for (int j = 0; j <B.length ; j++)            if (A[i]==B[j] && !visitedBs.contains(j))                for (int k = 0; k < C.length; k++)                    if (B[j] == C[k] && !visitedCs.contains(k)) {                        c++;                        visitedBs.add(j);                        visitedCs.add(k);                        break outerloop;                    }    return c;}有谁知道我应该如何降低时间复杂度？有没有办法用2个for循环代替？

Answer 1

将每个数组转换为映射，将出现的每个数字映射到该数字的出现次数 ( map.compute( (key,prev) -> (prev==null ? 1 : prev+1) ))。这需要 O(N)

计算所有映射中每个键的最小计数。也为 O(N)

将所有最小计数相加即可得出答案。也是 O(N)。

Answer 2

我想复杂性甚至更糟，因为 contains() 还执行 for 循环。

您可以创建3个包含A、B和C内容的集合，我将它们称为X_remaining。对于A_remaining中的每个元素，检查它是否包含在B_remaining和C_remaining中。如果是，则增加 c 并删除所有集合中找到的元素。尝试重复使用搜索结果，以免删除时再次搜索。

要比线性更快地查找元素，可以使用 TreeSet。也许 HashSet 也是您的一个选择。

Answer 3

这是一种实现O(n^2)此任务复杂性的方法：

private static int common(int[] A, int[] B, int[] C) { 

  List<Integer> listA = Arrays.stream(A).boxed().collect(Collectors.toList());

  List<Integer> listB = Arrays.stream(B).boxed().collect(Collectors.toList());

  List<Integer> listC = Arrays.stream(C).boxed().collect(Collectors.toList());

  listA.retainAll(listB);

  listA.retainAll(listC);

  listB.retainAll(listA);

  listB.retainAll(listC);

  listC.retainAll(listA);

  listC.retainAll(listB);

  return Math.min(listA.size(), Math.min(listB.size(), listC.size()));

}

另外，IMO 你可以获得O(n)解决方案，例如：

private static long common(int[] A, int[] B, int[] C) {

  Map<Integer, Long> frequencyA = findFrequencies(A);

  Map<Integer, Long> frequencyB = findFrequencies(B);

  Map<Integer, Long> frequencyC = findFrequencies(C);

  Set<Integer> common = frequencyA.keySet();

  common.retainAll(frequencyB.keySet());

  common.retainAll(frequencyC.keySet());

  return frequencyA.entrySet().stream()

    .filter(e -> common.contains(e.getKey()))

    .mapToLong(e -> Math.min(e.getValue(), Math.min(frequencyB.get(e.getKey()), frequencyC.get(e.getKey()))))

    .sum();

}

private static Map<Integer, Long> findFrequencies(int[] A) {

  return Arrays.stream(A)

    .boxed()

    .collect(Collectors.groupingBy(Integer::intValue, Collectors.counting()));

}

Answer 4

您可以在此处使用 a HashMap，对于每个子列表，计算它在子列表中出现的次数。一个简单的 Haskell 程序如下所示：

import Data.Hashable(Hashable)

import Data.HashMap.Strict(HashMap, alter, elems, empty, intersectionWith)

import Data.Maybe(maybe)

toCounter :: (Eq a, Hashable a, Integral i) => [a] -> HashMap a i

toCounter = foldr (alter (Just . maybe 1 (1+))) empty

mergeCount :: (Eq a, Hashable a, Integral i) => HashMap a i -> HashMap a i -> HashMap a i

mergeCount = intersectionWith min

然后我们可以用以下方法计算结果：

calculateMinOverlap :: (Eq a, Hashable a, Integral i, Functor f, Foldable f) => f [a] -> i

calculateMinOverlap = sum . elems . foldr1 mergeCount . fmap toCounter

然后我们可以计算最小重叠：

Main> calculateMinOverlap [[1,3,3,3,6], [3,3,1,5], [3,3,1,5,2]]

3

它需要元素总数的线性时间，并且该函数可以处理任意数量的子列表（假设至少有一个子列表）。

所需toCounter时间与子列表大小呈线性关系O(m)。当我们执行 an 时，我们将在O(n)fmap toCounter中处理所有列表，其中n是元素总数。

接下来的mergeCount工作时间为O(m 1 +m 2 )，其中m 1和m 2HashMap分别是两个 s中的元素数量。它每次都会返回一个HashMap包含多个元素的元素，该元素最多是两个元素中最小的一个。这意味着我们的foldr1 mergeCount工作时间也是O(n)。

最后，我们在O(m)中检索elems结果的 ，其中m是最终 中的元素数量，并且也需要O(m) 。HashMapsum

请注意，严格来说，对于巨大的数字，两个任意大数字的最小值等需要O(log v)，其中v是该数字的值。对于递增等也是如此。因此，如果对象数量很大，严格来说，它可以以O(n log n)进行缩放。