javascript - 我的 JS 字谜图解决方案的时间、空间复杂度

Question

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

目标是找到从A到B的索引映射P。映射 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]

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

尽管由于哈希，结果是使用时间O(1)生成的，但总的来说，我认为时间是O(n) code> 因为 n 是数字。我的想法正确吗？

大家对此有何看法？ (如果我是对还是错，不确定)。

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

Answer 1

扩展运算符 (...acc) 是 an O(n) operation覆盖正在传播的物体。这会大大影响你的时间复杂度。

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

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

哈希:时间 = 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)。