w******j
发帖数: 185 | 1 http://discuss.leetcode.com/questions/49/binary-tree-level-orde
Complexity Analysis:
Although the DFS solution traverse the same node multiple times, it is not
another order slower than the BFS solution. Here is the proof that the DFS
solution above runs in O(N) time, where N is the number of nodes in the
binary tree and we assume that the binary tree is balanced.
We first compute the complexity of printLevel for the kth level:
T(k) = 2T(k-1) + c
= 2k-1 T(1) + c
= 2k-1 + c
Assuming it's a balanced binary tree, then it would have a total of lg N
levels.
Therefore, the complexity of printing all levels is:
T(1) + T(2) + ... + T(lg N)
= 1 + 2 + 22 + ... + 2lg N-1 + c
= O(N)
T(k)那个倒是明白，但是traverse kth level的时候不是1 - k-1都要再来一遍吗？
这样的话，就喝底下哪个公式不符了吧.... | w******j
发帖数: 185 | | r*******e
发帖数: 7583 | 3 T(k)本身就是travese 1到k层的cost，不是单单访问第k层的
【在 w******j 的大作中提到】
: http://discuss.leetcode.com/questions/49/binary-tree-level-orde
: Complexity Analysis:
: Although the DFS solution traverse the same node multiple times, it is not
: another order slower than the BFS solution. Here is the proof that the DFS
: solution above runs in O(N) time, where N is the number of nodes in the
: binary tree and we assume that the binary tree is balanced.
: We first compute the complexity of printLevel for the kth level:
: T(k) = 2T(k-1) + c
: = 2k-1 T(1) + c
: = 2k-1 + c
| w******j
发帖数: 185 | 4
可是，上面说
T(1) = 1, T(2) = 2, T(3) = 2^2.....
但是我怎么觉得T(2)就是1 + 2 = 3,
T(3) = T(2) + 4 = 7?
我哪里想错了吗？
【在 r*******e 的大作中提到】
: T(k)本身就是travese 1到k层的cost，不是单单访问第k层的
| r*******e
发帖数: 7583 | 5 T(1) = 1
T(2) = 2*T(1) + c
T(3) = 2*T(2) + c
没看懂你的T(3) = T(2) + 4 是怎么来的
【在 w******j 的大作中提到】
:
: 可是，上面说
: T(1) = 1, T(2) = 2, T(3) = 2^2.....
: 但是我怎么觉得T(2)就是1 + 2 = 3,
: T(3) = T(2) + 4 = 7?
: 我哪里想错了吗？
| w******j
发帖数: 185 | 6
好像有点明白了....汗....谢谢你！
【在 r*******e 的大作中提到】
: T(1) = 1
: T(2) = 2*T(1) + c
: T(3) = 2*T(2) + c
: 没看懂你的T(3) = T(2) + 4 是怎么来的
|
|
