b****z
发帖数: 176 | 1 用queue 做树的广度优先遍历，空间复杂度是多少？
感觉好像不是O(n), 应该会比O(n)小？ 因为 空间复杂度应该是 树的底部的节点的数
量，因为每次都会dequeue。
大家觉得呢？ |
x****g
发帖数: 1512 | 2 性质不变，最大(N+1)/2 ?
【在 b****z 的大作中提到】
: 用queue 做树的广度优先遍历，空间复杂度是多少？
: 感觉好像不是O(n), 应该会比O(n)小？ 因为 空间复杂度应该是 树的底部的节点的数
: 量，因为每次都会dequeue。
: 大家觉得呢？
|
w*****h
发帖数: 423 | 3 树的底部节点数最多就n/2啊
【在 b****z 的大作中提到】
: 用queue 做树的广度优先遍历，空间复杂度是多少？
: 感觉好像不是O(n), 应该会比O(n)小？ 因为 空间复杂度应该是 树的底部的节点的数
: 量，因为每次都会dequeue。
: 大家觉得呢？
|
b*****a
发帖数: 70 | 4 Assuming you are talking about tree traversal of a binary tree. If n is the
total number of nodes, the space complexity of BFS using queue is O(n / 2). |
A*********c
发帖数: 430 | 5 The basic definition of complexity is "worst case", so it is just O(n).
Imagine a tree with 2 levels.
First level is root.
Second level contains 1000 nodes.
Even if the queue does not store all the nodes, it is still the Order of N.
so it is just plain O(n).
light?
【在 b****z 的大作中提到】
: 用queue 做树的广度优先遍历，空间复杂度是多少？
: 感觉好像不是O(n), 应该会比O(n)小？ 因为 空间复杂度应该是 树的底部的节点的数
: 量，因为每次都会dequeue。
: 大家觉得呢？
|
b****z
发帖数: 176 | 6
Thank you ! I got it !!
【在 A*********c 的大作中提到】
: The basic definition of complexity is "worst case", so it is just O(n).
: Imagine a tree with 2 levels.
: First level is root.
: Second level contains 1000 nodes.
: Even if the queue does not store all the nodes, it is still the Order of N.
: so it is just plain O(n).
: light?
|
b****z
发帖数: 176 | 7
Thank you ! I got it !!
【在 x****g 的大作中提到】
: 性质不变，最大(N+1)/2 ?
|
b****z
发帖数: 176 | 8
Thank you ! I got it !!
【在 w*****h 的大作中提到】
: 树的底部节点数最多就n/2啊
|
b****z
发帖数: 176 | 9
the
Thank you ! I got it !!
【在 b*****a 的大作中提到】
: Assuming you are talking about tree traversal of a binary tree. If n is the
: total number of nodes, the space complexity of BFS using queue is O(n / 2).
|
