java - dfs的空间复杂度

Question

我正在尝试分析以下算法的空间复杂度:

 /**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
     public int depthSum(List<NestedInteger> nestedList) {
        return helper(nestedList, 1);

    }
    public int helper(List<NestedInteger> nestedList, int depth){
        if(nestedList == null || nestedList.size() == 0){
            return 0;
        }
         int sum = 0;
         for(NestedInteger list : nestedList){
             if(list.isInteger()){
                  sum = sum + depth * list.getInteger();
            }
             if(list.getList() != null){
                 sum = sum + helper(list.getList(), depth + 1);
            }
        }
        return sum;

    }
}

空间复杂度应为 O(D)，其中 $D$ 是输入中的最大嵌套级别。为什么这是真的？

我的分析:根据 Google 的说法，空间复杂度是指在最坏的情况下，算法中的任何点需要多少内存。因为Java是按值传递的，所以每次调用辅助函数时，我们都需要额外的输入空间，所以我们使用的内存最多的是当我们第一次调用辅助函数时，它占用的空间等于之前使用的空间。保留看起来不是 O(D) 的输入。

Answer 1

因为您通过 call stack 的深度来确定空间复杂度加上例程分配的任何其他数据结构，那么我同意嵌套列表上的 DFS 为 O(d)，其中 d 是树的最大深度。让我们看一下典型树上的 DFS:

    a
   / \
  b   e
 / \
c   d 

DFS将调用以a为根的递归函数:

    a

它的第一个 child 将被访问:

    a
   /
  b

    a
   /
  b
 /
c

此时，DFS 碰到了一片叶子并开始回溯。我们已经达到了 DFS 将消耗的最大内存。

    a
   /
  b

下一个叶子匹配但不超过树的最大深度:

    a
   /
  b
   \
    d

    a
   /
  b

现在访问根的右子树:

    a
     \
      e

    a

我们就完成了。请记住，为每个节点创建一个调用堆栈帧，然后在访问该节点后将其弹出。

现在我们同意在任何时刻都不超过 d 个堆栈帧处于 Activity 状态，下一步是确定单个堆栈帧有多大。如果我们说服自己是O(1)，即输入的大小对栈帧大小没有影响，那么我们的整体复杂度是O(d) >.

这个问题的答案是，虽然Java是按值传递的，但“值”并不是内存中列表数据结构的副本。相反，它只是对数据结构的引用。引用的大小是恒定的，因此每帧有固定的开销。

.-------------- heap memory ---------------.
| ... [the actual list data in memory] ... |
`--------------------^---------------------`
                     |
    +----------------+
    |                |
.---|- frame 0 ----. |
|  nestedList sum  | |
`------------------` |
                     |
    +----------------+ 
    |                |
.---|- frame 1 ----. |
|  nestedList sum  | |
`------------------` |
                     |
    +----------------+ 
    |
.---|- frame 2 ----.
|  nestedList sum  |
`------------------`

上图过于简单化；这些列表引用并不都指向外部列表，而是指向外部列表的子列表，所以实际情况更像是:

.------------------ heap memory ------------------.
| ... [list] ... [list] ... [list] ... [list] ... |
`-------^------------^--------^-------------------`
        |            |        |
    +---+            |        |
    |                |        |
.---|- frame 0 ----. |        |
|  nestedList sum  | |        |
`------------------` |        |
                     |        |
    +----------------+        |
    |                         |
.---|- frame 1 ----.          |
|  nestedList sum  |          |
`------------------`          |
                              |
    +-------------------------+ 
    |
.---|- frame 2 ----.
|  nestedList sum  |
`------------------`

但是，所有堆内存都是在函数运行之前分配的；函数中的任何地方都没有 new(并且没有调用本身调用 new 的函数)。这是一个纯粹的遍历/搜索例程，有几个指向内存的小变量。

如果您仍然不相信，可以使用内存分析器以不同的数据结构运行此代码并绘制结果。这应该给出与数据结构深度成比例的线性图。