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 子分支。换句话说，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?
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 回答