假设一个节点(在 BST 中)定义如下(忽略所有的 setter/getter/inits)。
class Node
{
Node parent;
Node leftChild;
Node rightChild;
int value;
// ... other stuff
}
给定一些Node
在 BST 中的引用(称为startNode
)和另一个Node
(称为target
),一个是检查包含的树是否startNode
有任何节点value
等于target.value
。
我有两种算法可以做到这一点:
算法#1:
- From `startNode`, trace the way to the root node (using the `Node.parent` reference) : O(n)
- From the root node, do a regular binary search for the target : O(log(n))
T(n) = O(log(n) + n)
算法 #2:基本上执行 DFS(仅限伪代码)
current_node = startnode
While the root has not been reached
go up one level from the current_node
perform a binary-search from this node downward (excluding the branch from which we just go up)
这个算法的时间复杂度是多少?
天真的答案是O(n * log(n))
,where n
is for the while
loop,因为最多有n
节点,并且log(n)
是二分搜索。但很明显,这是高估了!
我能想出的最好(部分)答案是:
假设每个子分支都有一些
m_i
节点并且有k
子分支。换句话说,k
是startNode
与根节点之间的节点数总时间将是
.
T(n) = log(m1) + log(m2) + ... + log(mk)
= log(m1 * m2 * ... * mk)
Where m1 + m2 + ... + mk = n (the total number of nodes in the tree)
(这是我能得到的最好的估计,因为我忘记了大部分数学要做得更好!)
所以我有两个问题:
0) What is the time-complexity of algorithm #2 in terms of n
1) Which algorithm does better in term of time-complexity?