基本的DFS空間使用情況

Question

我有一個與空間使用有關的基本問題，我以DFS爲例。我不確定在這幾個實現中的空間使用是否相同，或者少數實際的不同。我對空間使用的解釋與功能分配直接相關。 任何人都可以幫助我驗證這幾個例子的空間使用情況嗎？這是關於空間複雜性的問題，而不是時間+功能

示例1：我們分配一個將存儲N個節點的字典。我肯定這個分配O（N）空間。

class Node: 
    def __init__(self, children): 
     self.children = children 

    def getChildren(self): 
     return self.children 

def dfs(start): 
    stack = [] 
    visited = {} 
    stack.append(start) 
    while(len(stack) > 0): 
     node = stack.pop() 
     if(node not in visited): 
      visited[node] = True 
      for child in node.getChildren(): 
       stack.append(child) 

例2：我們沒有在dfs函數中分配任何東西，而是我們給了一個標誌來設置節點。我們沒有在dfs函數中分配任何東西，所以它是O（1）空間使用情況。

class Node: 
    def __init__(self, children): 
     self.children = children 
     self.visited = False 

    def getChildren(self): 
     return self.children 

    def getVisited(self): 
     return self.visited 

    def setVisited(self, visit): 
     self.visited = visit 

def dfs(start): 
     stack = [] 
     stack.append(start) 
     while(len(stack) > 0): 
      node = stack.pop() 
      if(!node.getVisited()): 
       node.setVisited(True) 
       for child in node.getChildren(): 
        stack.append(child) 

示例3：我們有一個對象可以被操作的節點，但事先沒有標誌屬性。 DFS在每個節點上手動創建一個標誌，從而分配O（N）空間。

class Node: 
    def __init__(self, children): 
     self.children = children 

    def getChildren(self): 
     return self.children 

def dfs(start): 
    stack = [] 
    stack.append(start) 
    while(len(stack) > 0): 
     node = stack.pop() 
     if(node.visited is not None): 
      node.visited = True 
      for child in node.getChildren(): 
       stack.append(child) 

Answer 1

Space complexity不受其中的空間被分配但通過多少空間（存儲器）需要保持在相對於給定的數據結構，以對象的數目確定爲通過一種算法來處理。

在你的例子所有的數據結構需要O（N），空間（N =節點＃）