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 实现对于基本数组操作（例如创建一个大小为 n 的新数组）具有不同的时间复杂度。Javascript 数组通常被实现为动态数组或哈希表，并且这些数据结构具有不同的性能特征。

\n\n

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

\n\n

无论哪种方式，您的算法的最坏情况是当x = \'aa...aa\'和 时y = \'abb...bb\'，即x是 的 n 个副本\'a\'，并且y后跟\'a\'的 (m - 1) 个副本\'b\'。

\n\n

对于动态数组或哈希表，仅splice操作的时间复杂度为 O(nm\xc2\xb2)。这是因为外层循环迭代 O(nm) 次（注意i--循环内部，每次\'b\'需要删除字母时都会发生），并且该操作需要对after indexsplice中的 O(m) 个元素进行移位或重新编号。yArri

\n\n

但是假设使用一些更奇特的数据结构，它支持在亚线性时间内删除元素（例如，跳跃列表）。在这种情况下，上面只给出了“删除”操作的复杂度 O(nm) 倍。但我们还没有数过concat；这会创建一个新的数据结构并将每个项目复制到其中，这仍然需要线性时间。concat被调用 O(n) 次，每次调用平均花费 O(n + m) 时间，因此仅操作的复杂度concat就是 O(n\xc2\xb2 + nm)。

\n\n

所以时间复杂度很可能是 O(n\xc2\xb2 + nm\xc2\xb2)，并且肯定至少是 O(n\xc2\xb2 + nm)；不是线性的。

\n\n\n\n

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

\n