6

このJavaメソッドの再帰式を探すのにちょっと手詰まりです

void printInorder(Node<T> v) {
    if(v != null) {
        printInorder(v.getLeft());
        System.out.println(v.getData());
        printInorder(v.getRight());
    }
}

いくつかの基準:

  • 完全な二分木です (すべての内側の結び目に 2 つの子があり、すべての葉の深さが同じです)
  • ツリーには n ノットと O(n) の複雑度があります

depth hでツリーのに関連する再帰式を見つけるn knots必要があり、追加のボーナスとして、そこから O(n) につながる明示的な式を推定する必要があります。

今、これは私が得たものです：

d = depth of the tree
c = constant runtime for execution of the method itself
d = 1: T(n) = c
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c

私は例 d = 3 を使用して自分自身を明確にしましたが、これをさらに分解するのは困難です。私の仮定は正しいですか？

編集：次の試み

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number
d = 1: T(d) = 1
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1)))

1: T(h)  = T(i = 0) + T(i = 1) + ... T(i = h-1)
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2)))
3: T(h)  = n + n + ... + n
4: T(h)  = (h-1)n
5: T(h)  = O(n)

ツリーの深さの各レベルには正確に 2^(h-1) ノードが含まれているため、4 行目の h 係数は無視できます。これは、n が最終結果により関連するためです。

4

2 に答える 2

4

T(n) = T(n/2) + T(n/2) + 1

  • レベル 0 には 1 つの操作があります。

  • レベル 1 には 2 つの操作があります。

  • レベル 2 には 4 つの操作があります。

  • レベル k には 2^k 操作があります。

  • ツリーの深さは lgn です。

1+2+...+2^lgn=
2^0+2^1+2^2+...+2^lgn=
(2^(lgn + 1)-1)/(2-1)= 2*2^lgn=
2n.

于 2012-07-09T12:56:22.637 に答える
2

これは、Smoothness ルール (Levitin、 The Design & Analysis of Algorithms、第 2 版、481-82)を使用した代替アプローチです。これにより、このような再帰関係を代わりに指数として表すことができます。

滑らかさのルールのデモンストレーション。

この問題には、前方置換または後方置換のいずれかのアプローチが適しています。多くの場合、後方置換の方が消化しやすいと思います。

于 2012-07-09T13:42:30.107 に答える