1

n=B-A+1 と仮定すると、このアルゴリズムの再帰関係を導出する必要があります。

void recurringalgorithm(int *a, int A, int B){
  if (A == B){
    for (int j=0;j<B;j++){
      cout<<a[j];  
    }
    cout<<endl;
    return;
  }
  for (int i=A;i<B;i++){
    dosomething(a[A],a[i]);
    recurringalgorithm(a,A+1,B);
    dosomething(a[A],a[i]);
  }
}

ヘルプ？

4

1 に答える 1

4

再帰アルゴリズムの複雑さが であると仮定しますh(A,B)。

hコードから、次の2 つのケースに分けることができます。

h(A,B) = { complexity-of-if-branch          if A = B
         { complexity-of-rest-of-the-code   otherwise

「分岐の複雑さ」は些細なことです。「残りのコードの複雑さ」についてはrecurringalgorithm、 が含まれるため、再度含める必要がありますh。

たとえば、関数が次のように定義されている場合

function hh(A,B) {
    for (var i = A+1; i < B; ++ i)
        hh(i, B);
}

次に、複雑さは次のようになります

hh(A,B) = hh(A+1, B) + hh(A+2, B) + ... + hh(B-1, B)

これをコードと比較して一般化できます。

(ところで、複雑さはh(A,B) = O(B * (B-A)!))

于 2010-02-04T07:03:07.793 に答える