Как указано в комментариях, поскольку каждый элемент действительно затрагивается только один раз, временная сложность интуитивно O(N)
.
Однако, поскольку каждый рекурсивный вызов flatten
создает новый промежуточный массив, время выполнения сильно зависит от структуры входного массива.
Нетривиальным 1 примером такого случая может быть случай, когда массив организован аналогично полному двоичному дереву:
[[[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
push-операции O(k)
амортизируются, что не гарантируется стандартом, но все еще верно для большинства реализаций.
«истинное» O(N)
решение будет напрямую добавляться к выходному массиву final вместо создания промежуточных массивов:
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).