print bst in level order dfs为什么是O(N)不应该是O(N^2)吗?# JobHunting - 待字闺中
w*j
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都要再来一遍吗？
这样的话，就喝底下哪个公式不符了吧....
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都要再来一遍吗？
这样的话，就喝底下哪个公式不符了吧....
