algorithm - 为什么在 Anagram 映射中 O(n^2) 比 O(n) 快？

Question

给定两个列表 A 和 B，B 是 A 的变位词。B 是 A 的变位词意味着 B 是通过随机化 A 中元素的顺序得到的。我们想要找到从 A 到 B 的索引映射 P . 映射 P[i] = j 表示 A 中的第 i 个元素出现在 B 中的索引 j 处。这些列表 A 和 B 可能包含重复项。

例如给定

A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28] 我们应该返回 [1, 4, 3, 2, 0]

我的解决方案是 O(n^2)

public int[] anagramMappings(int[] A, int[] B) {
    int[] result = new int[100];
    int count = 0;
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < B.length; j++) {
            if (A[i] == B[j]) {
                result[i] = j;
                count++;
                break;
            }
        }
    }
    int[] tempArray = new int[count];
    for (int i = 0; i < count; i++) {
        tempArray[i] = result[i];
    }
    return tempArray;
}

这是我认为可能比上述解决方案更有效的另一种解决方案。我这样说是因为我用不同的输出测试了两个片段，第一个片段几乎总是执行得更快。

请说明为什么第一个片段比第二个片段快。我相信第二个更有效，复杂度为 O(n)

public int[] anagramMappingsx(int[] A, int[] B) {
    int[] res = new int[A.length];
    int index = 0;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < B.length; i++) {
        if (!map.containsKey(B[i])) {
            map.put(B[i], i);
        }
    }
    for (Integer i : A) {
        if (map.containsKey(i)) {
            res[index++] = map.get(i);
        }
    }
    return res;
}

Answer 1

Big-O 分析假设 N 非常大。它是关于当 N 趋于无穷大时复杂性会发生什么。因此，例如，O(n + 100) 与 O(n) 相同。但显然对于较小的 N 和较大的常数，情况并非如此。

在您的情况下，您的输入很小，并且您的 O(n) 算法使用的是非常复杂的数据结构，需要散列和表查找(加上处理存储桶未命中和其他所有问题)。您的 O(n^2) 算法不执行任何操作。从长远来看， map 可以弥补这一成本，但在短期内肯定不会。

通常，对于大多数语言中的小型数据集，您应该期望数组是可用的最快数据结构，即使它们迫使您使用 O(n^2) 算法。通常需要多个元素才能收回更复杂数据结构的成本。

由于内存局部性和编译器优化(尽管这取决于您的语言)，数组也往往比其他数据结构更快。内存局部性、减少分配/取消分配以及消除动态分派(dispatch)对实际性能的影响通常与大 O 复杂性分析一样多或更多。

令人遗憾的是，CS 程序和白板面试过于关注大 O 分析，就好像它是性能的开始和结束。性能远不止算法的复杂性

如果你想看到你的 O(n) 算法把你的 O(n^2) 算法打败，试着用 10k 或 10M 个元素运行它们，而不是 5 个。在这些规模上，big-O 更有可能占据主导地位情况。