以下算法的时间复杂度

Question

假设一个节点(在BST中)定义如下(忽略所有的setters/getters/inits)。

class Node
{

     Node parent;
     Node leftChild;
     Node rightChild;
     int value;
     // ... other stuff
}

给定一些对BST中的Node (称为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 (仅限于Psuedo代码)

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))，其中n用于while循环，因为最多有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?

Answer 1

好的，在翻阅我以前的数学书籍之后，我找到了k数的上界，其和是n是p <= (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)？或者这是否足以进行大O分析？)