递归深度展平的时间复杂度 [英] Time complexity for recrusive deep flatten

问题描述

此递归展平函数的运行时是什么?我的猜测是线性的.有人可以解释为什么吗?

What is the runtime for this recursive flatten function? My guess is that it's linear; can someone explain why?

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;
}

推荐答案

正如注释中指出的那样，由于每个元素确实只被触摸了一次，因此时间复杂度直观地显示为 O(N).

As pointed out in the comments, since each element is indeed touched only once, the time complexity is intuitively O(N).

但是，由于每次对flatten的递归调用都会创建一个新的中间数组，因此运行时在很大程度上取决于输入数组的结构.

However, because each recursive call to flatten creates a new intermediate array, the run-time depends strongly on the structure of the input array.

---

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

---

A non-trivial¹ example of such a case would be when the array is organized similarly to a full binary tree:

[[[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

时间复杂度递归关系为:

The time complexity recurrence relation is:

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

其中2 * T(n / 2)来自对flatten子树的递归调用，而O(n)来自push ing ² 的结果，它们是长度为n / 2的两个数组.

Where 2 * T(n / 2) comes from recursive calls to flatten the sub-trees, and O(n) from pushing² the results, which are two arrays of length n / 2.

大师定理指出在这种情况下 T(N) = O(N log N) ，而不是预期的O(N).

The Master theorem states that in this case T(N) = O(N log N), not O(N) as expected.

_{1)非平凡表示没有不必要的包装元素，例如[[[a]]].}

_{1) non-trivial means that no element is wrapped unnecessarily, e.g. [[[a]]].}

_{2)这隐式地假定k推送操作是O(k)摊销的，这不是标准所保证的，但是对于大多数实现而言仍然是正确的.}

_{2) This implicitly assumes that k push operations are O(k) amortized, which is not guaranteed by the standard, but is still true for most implementations.}

"true" O(N)解决方案将直接附加到 final 输出数组，而不是创建中间数组:

A "true" O(N) solution will directly append to the final output array instead of creating intermediate arrays:

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)，这是线性的.

The recurrence becomes T(n) = 2 * T(n / 2) + O(1) for the previous example, which is linear.

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

这篇关于递归深度展平的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！