JavaScript - 循环中 splice 和 concat 的时间和空间复杂度

Question

我是一个有用的助手，可以为您翻译文本。

我有一个问题，需要将一个字符串通过添加其初始值的副本来转换为另一个字符串。该问题允许在某些位置删除单个字符。

说明：

let x = "abba"; // First string
let y = "aba" // Second initial string

y("aba") => remove last "a" => y("ab") => y+initialY = "ab"+"aba" => 
y("ababa") => remove char at index 2 => y("abba") => y == x => sucess

我的算法成功地解决了这个问题：

let x = "abbbbcccaaac"
let y = "abc"

let xArr = x.split('')
let yArr = y.split('')

let count = 0;

for (let i = 0; i < xArr.length; i++) {
  if(yArr[i] == undefined) {
    yArr = yArr.concat(y.split(''));  
    count++;
  }
  if(xArr[i] != yArr[i]) {
    yArr.splice(i, 1);
    i--;
  }
}

console.log("Output is:", yArr.join(''))
console.log("Appends in order to transform:", count)

这个算法可以正常运行，但我对它的时间复杂度、空间复杂度以及最重要的效率感到不确定。

1. 这个算法的时间复杂度是O(n)，其中n是x的长度吗？

2. 如果这个算法的时间复杂度不是O(n)，那么问题能否在O(n)时间内解决？

3. 由于.concat()、.splice()或.split()嵌套在循环中，它们是否会改变时间复杂度？如果它们不是嵌套在循环中，它们是否仍然会改变算法的时间复杂度，改变程度如何？

4. 根据这个问题的规则，这是一种有效的解决方法吗？

5. 这个算法的空间复杂度是多少？

- user9410919

---

实际上，如果我们真的知道splice、split或concat的时间复杂度，那么它显然会影响算法的整体时间复杂度。但由于我们不知道，我们将把它们视为常数操作O(1)，这实际上使循环操作保持在O(N) - 最坏情况下。空间复杂度为O(1)，因为我们不会为每个循环操作创建新的存储（在这种情况下是计数），而只是更新它。在我看来，这是一个公平的解决方案，因为我不知道您所给出的问题的约束条件是什么。 - Caleb Lucas

@CalebLucas “但是既然我们没有，我们会将它们视为常量操作” - 我们应该吗？如果这样的话，这个问题还有意义吗？此外，ECMA规范提供了关于它们的提示。 - meowgoesthedog

@meowgoesthedog "我们应该吗？" - 我觉得这取决于一个人的目标。这些函数由JavaScript引擎在运行时进行优化。如果目的是真正深入了解每个函数及其在特定场景中的应用，那么考虑它们的时间复杂度就非常重要了。 - Caleb Lucas

@CalebLucas 你说得对，split()，concat()等方法已经被JS引擎优化了。但这并不意味着这些操作没有时间/空间复杂度。根据问题的意图，有两个答案。如果这是面试问题，那么我们需要考虑这些方法的时间和空间复杂度。如果是为应用程序而编写代码，则无需担心。看到这个问题，似乎是一个面试问题，因此OP需要考虑这些事情，因为下一个问题将是这个算法的复杂度是什么。 - Viral

Answer 1

通常像这样的问题很难给出明确的答案，因为不同的JavaScript实现对基本数组操作（如创建大小为n的新数组）有不同的时间复杂度。JavaScript数组通常被实现为动态数组或哈希表，这些数据结构具有不同的性能特点。

因此，没有一个确定的时间复杂度可以用来从数组中删除一个元素。我们可以说，对于动态数组，删除一个元素需要线性时间；正如@Ry-在评论中指出的那样，对于哈希表，也需要线性时间，因为需要重新编号后面的索引。我们还可以说，极有可能使用这两个数据结构之一，没有明智的实现会花费超过线性时间来执行splice。

无论如何，对于您的算法而言，最坏的情况是当x = 'aa...aa'和y = 'abb...bb'时，即x是'a'的n个副本，y是'a'后跟（m-1）个'b'。

对于动态数组或哈希表，仅进行splice操作的时间复杂度为O(nm²)。这是因为外部循环迭代了O(nm)次（请注意循环内部的i--，每次需要删除字母'b'时都会发生），并且splice操作需要在索引i之后移动或重新编号yArr中的O(m)个元素。

假设使用了一种更加奇特的数据结构，支持在次线性时间内删除元素（例如 跳表）。在这种情况下，上述算法只会使“删除”操作的复杂度增加 O(nm) 倍。但我们还没有计算 concat 操作；它创建一个新的数据结构并将每个项都复制到其中，这仍然需要线性时间。concat 被调用了 O(n) 次，并且每次调用平均需要 O(n+m) 的时间，因此仅 concat 操作的复杂度为 O(n²+nm)。

因此，时间复杂度很可能是 O(n²+nm²)，肯定不是线性的，至少是 O(n²+nm)。

---

空间复杂度为O(n)，因为yArr的长度永远不会超过xArr的两倍。

- kaya3

---

对于索引->值哈希表，splice(i, 1)不是O(1)，因为它必须重新编号所有内容。 - Ry-