以下算法的时间复杂度

假设节点（在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 （仅限伪代码）

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?

来源

2013-05-18 One Two Three

好的，在挖掘了我的旧数学书籍之后，我发现k数字的产品上限为n i s 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）？或者是否足够用于Big-O分析？）

来源

2013-05-18 21:53:39

以下算法的时间复杂度

回答

相关问题