0

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

我正在使用Tree具有分支因子或 10 的类来运行测试：

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来分析代码。

4

1 回答 1

4

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

于 2015-07-05T00:00:55.257 回答