Сложность времени для глубокого выравнивания

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 ² результатов, которые представляют собой два массива длины 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).}