为什么我的 Iterative Deepening Depth-First Search 实现占用的内存与 BFS 一样多？

Question

BFS 需要 O(b^d) 内存，而 IDDFS 运行 只需要 O(bd) 内存。但是，当我分析这两个实现时，结果发现它们使用的 RAM 量完全相同——我错过了什么？

我正在使用带有分支因子或 10 的 Tree class 到 运行 测试：

class Tree(object):
    def __init__(self, value):
        self.key = value
        self.children = [ ]

    def insert(self, value):
        if len(self.children) == 0:
            self.children = [ Tree(value) for x in range(10) ]
        else:
            for ch in self.children:
                ch.insert(value)

我的实现iddfs：

def iddfs(t):
    for i in range(0,8):
        printGivenLevel(t, i)

def printGivenLevel(t, level):
    if not t:
        return
    if level == 1:
        pass
    elif level > 1:
        for ch in t.children:
            printGivenLevel(ch, level - 1)

BFS 是

def bfs(t):
    currLevel = [t]
    nextLevel = []
    while currLevel:
        for node in currLevel:
            if node:
                nextLevel.extend([ x for x in node.children ])
        currLevel = nextLevel
        nextLevel = []

这段代码并没有真正做任何事情，只是遍历了整棵树。 我正在使用 https://github.com/fabianp/memory_profiler 来分析代码。

Answer 1

IDDFS 的内存优势仅适用于隐式树，其中节点在到达时生成并很快被丢弃。对于完全在内存中表示的树，树本身已经占用 O(b^d) 内存，相比之下，IDDFS 或 BFS 所需的内存较小。