Почему моя реализация итеративного углубления поиска в глубину занимает столько же памяти, сколько BFS?

Question

BFS требует O(b^d) память, тогда как известно, что IDDFS работает только O(bd) объем памяти. Однако при профилировании этих двух реализаций оказывается, что они используют одинаковый объем оперативной памяти - что мне не хватает?

Я использую 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 для профилирования кода.

Answer 1

Преимущества памяти IDDFS применимы только к неявному дереву, где узлы генерируются по мере их достижения и сбрасываются вскоре после этого. С деревом, представленным полностью в памяти, само дерево уже занимает O(b^d) памяти, и память, необходимая для IDDFS или BFS, незначительна по сравнению.