递归深度扁平化的时间复杂度

Question

这个递归展平函数的运行时间是多少？我的猜测是它是线性的；有人可以解释为什么吗？

const arr = [
  [14, [45, 60], 6, [47, [1, 2, [14, [45, 60], 6, [47, [1, 2]], 9]]], 9],
];

function flatten(items) {
  const flat = [];

  items.forEach(item => {
    if (Array.isArray(item)) {
      flat.push(...flatten(item));
    } else {
      flat.push(item);
    }
  });

  return flat;
}

Answer 1

正如评论中指出的那样，由于每个元素确实只接触一次，因此时间复杂度直观 O(N)。

但是，因为每次递归调用flatten都会创建一个新的中间数组，所以运行时间强烈依赖于输入数组的结构。

这种情况的一个非平凡的¹示例是当数组的组织方式类似于完整二叉树时：

[[[a, b], [c, d]], [[e, f], [g, h]]], [[[i, j], [k, l]], [[m, n], [o, p]]]

               |
        ______ + ______
       |               |
    __ + __         __ + __
   |       |       |       |
 _ + _   _ + _   _ + _   _ + _
| | | | | | | | | | | | | | | | 
a b c d e f g h i j k l m n o p

时间复杂度递推关系为：

T(n) = 2 * T(n / 2) + O(n)

Where2 * T(n / 2)来自flatten对子树的递归调用，以及O(n)来自pushing ²的结果，它们是两个长度为 的数组n / 2。

该主定理指出，在这种情况下 T(N) = O(N log N)，不会O(N)如预期。

_{1)非平凡意味着没有元素被不必要地包裹，例如[[[a]]].}

_{2) 这隐含地假设k推送操作是O(k)摊销的，标准不保证这一点，但对于大多数实现仍然如此。}

“真”O(N)解决方案将直接附加到最终输出数组，而不是创建中间数组：

function flatten_linear(items) {
  const flat = [];

  // do not call the whole function recursively
  // ... that's this mule function's job
  function inner(input) {
     if (Array.isArray(input))
        input.forEach(inner);
     else
        flat.push(input);
  }

  // call on the "root" array
  inner(items);  

  return flat;
}

T(n) = 2 * T(n / 2) + O(1)对于前面的示例，循环变为线性。

_{再次假设 1) 和 2)。}