JavaScript flatten array: 这两种方法在时间复杂度上是否相同？

Question

我知道存在数组方法 flat。但我想更好地了解 ... 和 concat 如何影响时间复杂度。

function flat1(arr) {
  return arr.reduce(
    (flatArr, item) => {
      flatArr.push(...(Array.isArray(item) ? flat1(item) : [item]))
      return flatArr
    },
    []
  )
}

function flat2(arr) {
    return arr.reduce(
      (flatArr, item) => {
        return flatArr.concat(Array.isArray(item) ? flat2(item) : item)
      },
      []
    )
  }

我的直觉是，这两种方法都采用 O(n^2) 时间复杂度的最坏情况，n 是原始数组中的项目数。因为 concat 和 ... 都将遍历数组，并且这两个操作都需要 n。我的理解对吗？

一种方法优于另一种方法吗？

Answer 1

我需要通过不递归展平来简化问题，而只是一个层次：

function flat1(arr) {
  return arr.reduce((flatArr, item) => {
    flatArr.push(...(Array.isArray(item) ? item : [item]))
    return flatArr
  }, [])
}

function flat2(arr) {
  return arr.reduce((flatArr, item) => {
    return flatArr.concat(Array.isArray(item) ? item : [item])
  }, [])
}

我们假设 arr 中的元素数为 n，每个 item 数组中的平均元素数为 m。（非数组的 item 计入该平均值为 1）。

both concat and ... are going to iterate through the array

是的，他们都需要遍历给他们的item。但这不是重点。 push 修改 flatArr 并花费 O(m) 时间向其添加 O(m) 新元素。

然而，concat 确实创建了一个新数组，为此它不仅需要迭代 item，还需要迭代 flatArr。鉴于 flatArr 平均包含 O(n/2*m) 个项目，flatArr.concat(item) 需要 O(n/2*m + m) = O(n*m).

由于对 arr 中的每个项目执行一次这些操作，我们得到

对于flat1时间复杂度O(n*m)和
对于flat2，时间复杂度O(n*n*m)更差。

递归函数的时间复杂度要复杂得多，因为它们还取决于您在哪些嵌套级别上有多少数组。我什至没有想出一个好的指标来描述这种数据结构:-)

JavaScript flatten array: 这两种方法在时间复杂度上是否相同？

JavaScript flatten array: are the two approaches the same in terms of the time complexity?

javascript

big-o