4

私は問題のいくつかの二分木セットのためのいくつかのコードを書きました...コードは次のとおりで、答えがイエスの場合は左、答えがノーの場合は右にツリーを下っていき、外部ノードに到達すると外部ノードを返します。

Javaで書かれた、

public static int price(BinaryTree<Integer> t, boolean[] p) {

    Position<Integer> root = t.root(); //1
    while (t.isInternal(root)) { //2

        int element = root.element();  // 3

        if (!p[element]) { //4
            root = t.getRight(root);//5
        }

        if (p[element]) { //6
            root = t.getLeft(root); //7
        }
    }
    int price = root.element(); //8
    return price; //9
}

大きな OI を計算するとき、上記のようにコメント内のコードのステップに番号を付けるのが最善だと思いました...ここの例に従いました

Big O さん、どのように計算/概算しますか?

したがって、上記の 1 ～ 9 は次のようなものと同等である必要があります。ここで、Cは定数であり???、私のループです (ここで、N は特定のデータ構造の入力の数です)。

C + ??? + C + ??? + C + ??? + C + C + C

私のwhileループは私が思うC*Nか、(O(N))むしろC*N今のところです）そして私の2つのifステートメントは（O(1)インデックス作成の時間の複雑さについて...そしてO(N)スペースの複雑さについては、今のところ時間の複雑さに固執します）

だから今私は持っているべきです（C要素を削除すると、それらは定数であり、実際には重要ではありません）

C*N + C + C時間の複雑さ

と

C*N + C*N + C*Nスペースの複雑さ

私が持っている意味

C*NまたはO (N)時間の複雑さと空間の複雑さ

O(3N)O(N)...と見なすことができるもの

だから私の質問は、私はこれを正しくやったのですか、そうでなければどこで間違ったのですか?

ありがとうございました

編集：

ツリーは、答えが真 (はい) の場合は左に移動し、いいえの場合は右に移動します。内部ノードには、ツリー内の m 個の内部ノードに対して 0 から m-1 までの番号が付けられます。したがって、ルート、内部ノード 0 で no が指定され、したがって右に移動する場合、この内部ノードはノード 3 である可能性があり、p[1] が答えであるため、ブール値の答えは p[1] ではなく p[3] にあります。ノード 1、つまり質問 1 の場合。混乱を招くお詫び

4

1 に答える 1

3

はいといいえ。

O(n)各要素を一定回数以上「タッチ」しないため、アルゴリズムは確かに です。

ただし、これは厳密な境界ではありません。つまり、そうではなくTheta(n)、そうですTheta(logN)。(大きな O は上限のみであることを忘れないでください)。

これは、ツリーのバランスが取れており、アルゴリズムが基本的にルートからツリー内のリーフへのパスを取得しているためです。左/右に移動することを「選択」すると、元には戻らないことに注意してください。基本的に、各高さのノードに一定の回数だけ「タッチ」して、アルゴリズムを作成します-木の高さはO(h)どこですか。h

ツリーはバランスが取れh < C * log(n)ているため、一定の定数についてC- これにより、アルゴリズムは次のようになります。Theta(logN)

于 2013-08-27T06:58:31.000 に答える