JavaScript指定数组处理代码的空间复杂度：如何计算与推导？

咱们先把要分析的代码摆出来：

a.filter(function(v) { return !b.includes(v); })

其中a是包含N个数字的数组，b是包含M个数字的数组。

接下来咱们一步步推导空间复杂度：

• 首先明确空间复杂度的核心：咱们算的是算法运行时额外开辟的存储空间，输入本身（也就是数组a和b）的空间不算在内，因为这是给定的输入资源。
• 先看filter方法的行为：filter会创建一个新数组来存放所有符合条件的元素。这个新数组的最大长度就是a的长度N——当a里的所有元素都不在b中时，所有元素都会被保留下来；最小长度是0——当a里的元素全在b中时。所以这部分额外空间的量级是O(N)。
• 再看b.includes(v)的开销：includes是线性遍历b数组来查找元素，这个过程只用到几个临时变量（比如循环的索引、当前比较的元素），这些都是常数级的空间，不会随N或M的大小变化，所以这部分是O(1)。
• 最后看回调函数：每次执行回调只是做一个简单的判断，没有开辟持续占用的大空间，属于常数级开销，不影响整体复杂度。

总结一下：这段代码的空间复杂度是O(N)，最坏情况下需要存储a中所有不在b里的元素，其他操作的空间开销都是常数级的。

内容的提问来源于stack exchange，提问作者dream123