为什么深度优先搜索的 space 复杂度不表示为 O(n)？
Why is the space complexity of depth-first search not expressed as O(n)?
算法相对较新，所以如果我遗漏了一些明显的东西，请原谅！
我知道深度优先搜索的space复杂度通常表示为O(h)，其中h是树的高度，而广度优先搜索的复杂度是O(n) ，其中 n 是树中的节点数。
我理解解释（例如在这个答案中），在 BFS 中最坏的情况下，所有节点都在一个级别上，这意味着我们必须在遍历所有节点之前将它们排队.我也明白 space 一棵树的复杂性将由它的高度决定，因为这将决定堆栈上需要存储的最大层数。
我不明白的是为什么这不也表示为 O(n)。沿着与 BFS 最坏情况类似的推理，DFS 最坏情况不是所有节点都在彼此之下，沿着一个单一的谱系吗？所以在最坏的情况下，树的高度将等于它拥有的节点数。那么为什么这不也表示为 O(n) 呢？
谢谢
是的，但这并不是真正的树，它是一个链表。 Big-O 是抽象的；当它声称对一棵树的搜索是 lg(n) 时，它意味着一棵适当平衡的树，而不是一棵病态构造的树。
算法相对较新，所以如果我遗漏了一些明显的东西，请原谅！
我知道深度优先搜索的space复杂度通常表示为O(h)，其中h是树的高度，而广度优先搜索的复杂度是O(n) ，其中 n 是树中的节点数。
我理解解释（例如在这个答案中），在 BFS 中最坏的情况下，所有节点都在一个级别上，这意味着我们必须在遍历所有节点之前将它们排队.我也明白 space 一棵树的复杂性将由它的高度决定，因为这将决定堆栈上需要存储的最大层数。
我不明白的是为什么这不也表示为 O(n)。沿着与 BFS 最坏情况类似的推理，DFS 最坏情况不是所有节点都在彼此之下，沿着一个单一的谱系吗？所以在最坏的情况下，树的高度将等于它拥有的节点数。那么为什么这不也表示为 O(n) 呢？
谢谢
是的，但这并不是真正的树，它是一个链表。 Big-O 是抽象的；当它声称对一棵树的搜索是 lg(n) 时，它意味着一棵适当平衡的树，而不是一棵病态构造的树。