0

二分木で実行できる操作であるさまざまな機能を書き留めています。

私は、この関数の実行時間を知りたいのですが、それらを取り除こうとしています:

  getMaxDepth(Tree) //What can be the time complexity here? 
    if Tree.root = NIL return 0 // BaseCase
    leftDepth := 1 + getMaxDepth(Tree.root.left)
    rightDepth := 1 + getMaxDepth(Tree.root.right)
    if leftDepth > rightDepth then return leftDepth;
    else return rightDepth;


  internalNodeCount(Node n) // And here?
    if isLeaf(n) then return 0
    return 1 + internalNodeCount(n.left) + internalNodeCount(n.right)

  isLeaf(Node n)
    return n=NIL OR (n.left=NIL AND n.right=nil);

GetMaxDepthノードごとにツリー全体を再帰的にトラバースする必要があるため、時間の複雑さは O(n) であると想定しています....良い説明は何ですか?

InternalNodeCount 同じ理由で同じ複雑さ O(n) だと思います.....

4

1 に答える 1

0

私が理解したことから、あなたは何らかの証拠を探しているようです。

getMaxDepth の説明は次のとおりです。

T(1) = c1
T(n) = T(k) + T(n-k-1) + c2
where
T(n) = Time to process tree of n nodes 
n = number of nodes
k = nodes in left subtree
n-k-1 = nodes in right subtree
c1, c2 = constants (not dependent upon n) 
(Time to calculate the depth of the tree from given left and right subtree depth)

定数が異なることを除いて、同じことが internalNode にも適用できます。

于 2013-02-23T03:38:15.950 に答える