为什么在 Anagram 映射中 O(n^2) 比 O(n) 快?
Why is O(n^2) faster than O(n) in anagram mapping?
给定两个列表A和B,B是A的变位词。B是A的变位词意味着B是通过随机化A中元素的顺序得到的。我们想从A中找到一个索引映射P到 B。映射 P[i] = j 表示 A 中的第 i 个元素出现在 B 中的索引 j 处。这些列表 A 和 B 可能包含重复项。
例如给定
A = [12, 28, 46, 32, 50]
B = [50, 12, 32, 46, 28]
我们应该 return
[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;
}
Big-O 分析假设 N 非常大。它是关于当 N 趋于无穷大时复杂性会发生什么。因此,例如,O(n + 100) 与 O(n) 相同。但显然对于小 N 和大常量,情况并非如此。
在你的情况下,你的输入很小,你的 O(n) 算法使用了一个非常复杂的数据结构,需要散列和 table 查找(加上处理桶未命中和所有其他)。您的 O(n^2) 算法会执行 none 的操作。地图可以在长运行中弥补这个成本,但在短运行中肯定不会。
通常,对于大多数语言中的小数据集,您应该期望数组是最快的可用数据结构,即使它们迫使您使用 O(n^2) 算法。通常需要多个元素才能收回更复杂数据结构的成本。
由于内存局部性和编译器优化(尽管这取决于您的语言),数组也往往比其他数据结构更快。内存局部性、减少 allocations/deallocations 和消除动态调度对现实世界性能的影响通常与 big-O 复杂性分析一样多或更多。
令人遗憾的是,CS 程序和白板面试过于关注大 O 分析,就好像它是性能的开始和结束。性能远不止算法复杂性
如果你想看到你的 O(n) 算法把你的 O(n^2) 算法打败,试试 运行用 10k 或 10M 个元素而不是 5 个元素来组合它们。在那些尺度上,大- O更有可能主导局面。
给定两个列表A和B,B是A的变位词。B是A的变位词意味着B是通过随机化A中元素的顺序得到的。我们想从A中找到一个索引映射P到 B。映射 P[i] = j 表示 A 中的第 i 个元素出现在 B 中的索引 j 处。这些列表 A 和 B 可能包含重复项。
例如给定
A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28] 我们应该 return [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;
}
Big-O 分析假设 N 非常大。它是关于当 N 趋于无穷大时复杂性会发生什么。因此,例如,O(n + 100) 与 O(n) 相同。但显然对于小 N 和大常量,情况并非如此。
在你的情况下,你的输入很小,你的 O(n) 算法使用了一个非常复杂的数据结构,需要散列和 table 查找(加上处理桶未命中和所有其他)。您的 O(n^2) 算法会执行 none 的操作。地图可以在长运行中弥补这个成本,但在短运行中肯定不会。
通常,对于大多数语言中的小数据集,您应该期望数组是最快的可用数据结构,即使它们迫使您使用 O(n^2) 算法。通常需要多个元素才能收回更复杂数据结构的成本。
由于内存局部性和编译器优化(尽管这取决于您的语言),数组也往往比其他数据结构更快。内存局部性、减少 allocations/deallocations 和消除动态调度对现实世界性能的影响通常与 big-O 复杂性分析一样多或更多。
令人遗憾的是,CS 程序和白板面试过于关注大 O 分析,就好像它是性能的开始和结束。性能远不止算法复杂性
如果你想看到你的 O(n) 算法把你的 O(n^2) 算法打败,试试 运行用 10k 或 10M 个元素而不是 5 个元素来组合它们。在那些尺度上,大- O更有可能主导局面。