以下算法的時間複雜度

假設節點（在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

以下算法的時間複雜度

回答

相關問題