1

假设一个节点(在 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 nis for the whileloop,因为最多有n节点,并且log(n)是二分搜索。但很明显,这是高估了!

我能想出的最好(部分)答案是:

  • 假设每个子分支都有一些m_i节点并且有k 子分支。换句话说,kstartNode与根节点之间的节点数

  • 总时间将是

.

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?
4

1 回答 1

1

好的,在翻阅了我的旧数学书籍之后,我能够找到总和为的k数字乘积的上限。np <= (n /k) ^k

话虽如此,该T(n)功能将变为:

T(n) = O(f(n, k))
Where
f(n, k) = log((n/k)^k)
     = k * log(n/k)
     = k * log(n) - k * log(k)

(记住,k 是 startNode 和根节点之间的节点数,而 n 是节点的总数)

我将如何离开这里?(即,我如何简化 f(n, k)?或者这对于 Big-O 分析是否足够好?)

于 2013-05-18T21:53:39.840 回答