Javascript-循环内拼接和连接的时间和空间复杂性

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()是否以某种方式更改了时间复杂度，因为它们嵌套在for循环中？如果不是的话，它们还会改变算法的时间复杂度以及改变多少吗？

4. 给出此问题的规则，这是解决问题的有效方法吗？

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

Answer 1

通常，这样的问题很难给出确切的答案，因为Javascript的不同实现对基本数组操作（例如creating a new array of size n）具有不同的时间复杂度。 Javascript数组通常将实现为dynamic arrays或hashtables，并且这些数据结构具有不同的性能特征。

因此，splice从数组中删除一个元素没有确定的时间复杂度。我们可以说的是，对于动态数组，删除一个元素需要线性时间，而对于哈希表则需要恒定时间。并且很可能使用了这两种数据结构中的一种，并且没有任何明智的实现需要比线性时间花费更多的时间splice。[无论哪种方式，对于您的算法，最坏的情况都是x = 'aa...aa'和y = 'abb...bb'，即x是'a'的n个副本，y是'a'，然后是[m-1]个[ C0]。

如果使用的数据结构是动态数组，则时间复杂度为O（n²m+nm²），其中n为'b'，m为x.length。这是因为外部循环迭代O（nm）次（请注意，循环内部每次需要删除字母y.length时都会发生i--），并且对平均长度为O的数组进行'b' （n + m）。

如果使用的数据结构是哈希表，则以上仅给出O（nm）。但是，您还在循环中使用splice，该循环创建一个新数组并将每个项目复制到其中。对于哈希表来说，这仍然需要花费线性时间，因此复杂度为O（n²+ nm），因为concat被称为O（n）次，并且每次调用平均需要O（n + m）次。

因此，结论是时间复杂度应为二次或更差，具体取决于数据结构；不是线性的。

---

空间复杂度为O（n），因为concat的长度永远不会超过yArr的两倍。