1

プログラム内の関数の時間計算量を見つける必要があります。指定されたキーを持つ三分木のすべての内部ノードを検索します。このツリーはランダムに埋められます。コードを書くことはできたと思いますが、複雑さを計算する方法がわかりません。

ツリーの関数と構造体は次のとおりです。

typedef struct _no
{
    int chave; 
    struct _no *F[3]; 
} TipoNo;

typedef TipoNo *TipoArvore;

int noSubTree (TipoArvore t, int x){
    int n;
    if (t == NULL){
        return 0;
    }
    else{
        if(t->F[0] == NULL && t->F[1] == NULL && t->F[2] == NULL ){
             return 0;
        }
        else if(t->chave == x) {                 
          return 1 + noSubTree(t->F[0], x) + 
                     noSubTree(t->F[1], x) + 
                     noSubTree(t->F[2], x);
        }
        else {
          return 0 + noSubTree(t->F[0], x) +
                     noSubTree(t->F[1], x) +
                     noSubTree(t->F[2], x);
       }
    }
 }

誰かが私にそれをどのように行うべきかを説明できれば、私は最も感謝しています。

4

2 に答える 2

0

これについて考える 1 つの方法は、次のように考えることです。

  • 各ノードが訪問された回数
  • ノードへのアクセスごとに実行される作業量。

コードがノードにアクセスするたびに O(1) が機能することに注意してください。これは、より多くの再帰呼び出しを開始し、オプションで結果に 1 つ追加するだけです。また、各ノードに 1 回だけアクセスします。各ノードはその子の関数のみを呼び出すため、最終的にはすべてのノードに到達し、すべての呼び出しは下向きでオーバーラップしないため、ノードが 2 回アクセスされることはありません。

したがって、合計時間計算量は Θ(n) です。ここで、n はツリー内のノードの合計数です。

まったく関係のないことですが、このコードは C で記述しているため、いくつかのケースをまとめて要約できます。たとえば、次のコード行を見てください。

if(t->chave == x) {                 
    return 1 + noSubTree(t->F[0], x) + 
               noSubTree(t->F[1], x) + 
               noSubTree(t->F[2], x);
}
else {
   return 0 + noSubTree(t->F[0], x) +
              noSubTree(t->F[1], x) +
              noSubTree(t->F[2], x);
}

C では、論理演算子==は、2 つの引数が等しい場合は 1 に評価され、そうでない場合は 0 に評価されます。したがって、これらのケースを次のようにまとめることができます。

return (t->chave == x) + noSubTree(t->F[0], x) +
                         noSubTree(t->F[1], x) +
                         noSubTree(t->F[2], x);

お役に立てれば！

于 2013-11-01T01:08:59.010 に答える
0

noSubTree()- ルートを開始点として指定すると、ツリーのすべてのノードにヒットしますが、各ノードには 1 回しかヒットしないため、この関数の複雑さは O(n) です。

検索の複雑さを知りたい場合、それはもう少し大きな問題です。バランスのとれた二分木の検索は、O(log 2 (n)) の複雑さを持ちます。平衡三分木の検索は O(log 3 (n)) になります。最悪の場合、不均衡なツリーの検索はすべてのノードを通過する必要があるため、複雑さは O(n) になります。

于 2013-11-01T01:31:39.240 に答える