java - dfs的空间复杂度

问题描述

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

 /**
 * // 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$ 是输入中的最大嵌套级别。为什么这是真的？

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

标签： javatime-complexity

解决方案

由于您通过调用堆栈的深度以及例程分配的任何其他数据结构来确定空间复杂度，因此我同意嵌套列表上的 DFS 是O(d)树d的最大深度。让我们看一下典型树上的 DFS：

    a
   / \
  b   e
 / \
c   d

DFS 将以aroot 身份调用递归函数：

它的第一个孩子将被访问：

    a
   /
  b

    a
   /
  b
 /
c

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

    a
   /
  b

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

    a
   /
  b

现在访问根的右子树：

    a
     \
      e

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

既然我们同意d在任何时刻只有堆栈帧处于活动状态，下一步就是确定单个堆栈帧的大小。如果我们说服自己它是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）。这是一个纯粹的遍历/搜索例程，有几个指向内存的小变量。

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

java - dfs的空间复杂度

问题描述

解决方案

推荐阅读