このアルゴリズムの漸化式を探しますか?
-
25-09-2019 - |
質問
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]);
}
}
ヘルプ?
解決
あなたの再帰アルゴリズムの複雑さはh(A,B)
であると仮定します。
あなたは2例にh
を分割することができます:
h(A,B) = { complexity-of-if-branch if A = B
{ complexity-of-rest-of-the-code otherwise
は、 "複雑-の-IF-ブランチは" 自明です。それは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)
あなたが一般化するためにあなたのコードでこれを比較することができます。
(BTW、複雑さがh(A,B) = O(B * (B-A)!)
である)
所属していません StackOverflow