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