此递归展平函数的运行时是什么?我的猜测是线性的.有人可以解释为什么吗?
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.
这种情况的一个非平凡的 1 例子是当数组的组织类似于完整的二叉树时:
A non-trivial1 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 2 的结果，它们是长度为n / 2的两个数组.
Where 2 * T(n / 2) comes from recursive calls to flatten the sub-trees, and O(n) from pushing2 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).