复发性深度扁平化的时间复杂度

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)

其中2 * T(n / 2)来自递归调用以flatten子树，O(n)来自push^{ing 2}的结果，这是两个长度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(。}