1

ノード (BST 内) が次のように定義されているとします (すべてのセッター/ゲッター/初期化を無視します)。

class Node
{

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

NodeBST ( と呼ばれるstartNode) と別のNode( と呼ばれる) のsome への参照が与えられた場合、targetを含むツリーに に等しいstartNodeノードがあるかどうかを確認します。valuetarget.value

これを行うには、次の 2 つのアルゴリズムがあります。

アルゴリズム #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はほとんどないため、 は二分探索を表します。しかし、明らかに、それは過大評価です!nlog(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)

(これは、数学のほとんどを忘れてしまったので、私が得ることができる最高の見積もりです!)

だから私は2つの質問があります：

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わかりました、古い数学の本を掘り下げた後、合計が である数値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) を単純化できますか? それとも Big-O 分析には十分でしょうか?)

于 2013-05-18T21:53:39.840 に答える