Временная сложность этого повторения?

Question

Я пытался выяснить сложность этого повторения во время выполнения, используя основную теорему. Я в некотором роде заблудился, поэтому, согласно основной теореме.

T (n) = aT (n / b)) + f (n)

Я подключаю значение

Сколько существует рекурсивных (разделенных) функций?

a = 1

Относительный размер подзадачи. На какую скорость уменьшается ввод?

b = L, поскольку подзадача является независимым списком

Время выполнения работы, выполненной вне рекурсии?

f (n) = n например, может не быть списка, только целое число

Какой случай основной теоремы применим к этому?

/*
341. Flatten Nested List Iterator on leetcode
 Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other 
lists.

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, 
          the order of elements returned by next should be: [1,1,2,1,1].
*/

void recurse(vector<NestedInteger>& nestedList){
    for(int i = 0 ; i < nestedList.size(); i++){
        if(nestedList[i].isInteger()){
            res.push_back(nestedList[i].getInteger());
        }else{
            recurse(nestedList[i].getList());
        }

    }
}

Answer 1

Эта конкретная рекурсивная проблема плохо смоделирована с использованием основной теоремы. Основная теорема хороша для рекуррентных отношений, где размер входных данных уменьшается на некоторый постоянный коэффициент при каждом рекурсивном вызове. В вашем случае это не обязательно так. Например, рассмотрите возможность выравнивания этого списка:

[[[[[[[[...[[[1]]]...]]]]]]]]]

Здесь каждый рекурсивный вызов только уменьшает размер списка на единицу, а не делится на некоторую константу. В результате вы не можете применить основную теорему здесь.

Я думаю, что вам больше повезет, анализируя эту рекурсию, если вы переосмыслите способ представления списка. Вы можете думать о своем списке как о бинарном дереве, где список представлен как цепочка узлов, перемещающихся вправо, а подсписок представлен как левое поддерево. Так, например, входные данные

[1, [2, 3], [[4]]

будут выглядеть следующим образом:

 1
  \
   *
  / \
 2   \
  \   \
   3   *
      /
     *
    /
   4

Ваш рекурсивный алгоритм выполняет O (1) каждый раз, когда посещает узел, плюс работу, необходимую для обработки правое поддерево (остальная часть списка) и левое поддерево (рекурсивный список, предполагая, что элемент является списком). В этом смысле вы посещаете каждый узел в двоичном дереве один раз, выполняя O (1) работы на узел, за net всего O (n) работы.