我的JS字谜地图解决方案的时间，空间复杂度

Question

当前设置，A和B可能是较大的字谜，但我在这里选择了一个简单的示例。

目标是找到从P到A的索引映射B。映射P[i] = j表示A中的第[n]个元素出现在B中的索引j处。

const A = [12, 28, 46, 32, 50]
const B = [50, 12, 32, 46, 28]

const hash = B.reduce((acc,cur,idx) => ({ ...acc, [cur]: idx }), {});

const result = A.reduce((acc,cur) => [...acc, hash[cur]], []);

return result

结果应该是

[1, 4, 3, 2, 0]

我认为我的解决方案的时间/空间复杂度是：hash：时间= O(a)，空格=O(c)结果：时间= O(b)，空格=O(d)最终答案是时间= O(a + b)，空格=O(c + d)关于时间和空间的最终最终答案是O(n)？

即使由于O(1)而使用时间hash生成结果，总的来说，我认为时间为O(n)，因为n是数字。我认为正确吗？

每个人对此有何想法？ （如果我是对还是错，则不确定）。

我想你们中的有些人会问为什么不使用indexOf()，根据我的研究，它看起来像是在一个引擎盖下循环了，所以我将运行O(2n)。因此，中型到大型的字谜都是致命的。

Answer 1

展开运算符（...acc）在要展开的对象上为an O(n) operation。这使您的时间变得很复杂。

此外，由于A和B是字谜，因此它们可以使用相同的符号n，因为它们的长度相同。

我不确定空间复杂度，但我认为时间复杂度将是：

hash：时间= O（n ^ 2）

结果：时间= O（n ^ 2）

最终答案是时间= O（2n ^ 2），即〜O（n ^ 2）。

---

建议的改进：

• 不要使用传播运算符，它是不必要的且缓慢。
• Array.map而不是Array.reduce，因为结果更干净
• [hash不会散列任何内容，因此名称不清楚，更多的是数字到索引的映射-map更加清晰]

const A = [12, 28, 46, 32, 50]
const B = [50, 12, 32, 46, 28]

const map = B.reduce((acc,cur,idx) => { acc[cur] = idx; return acc; }, {});
const result = A.map(cur => map[cur]);

console.log(result);

此版本是一个非常简单的O（2n）->〜O（n）。