Trova recidiva relazione di questo algoritmo?
-
25-09-2019 - |
Domanda
Supponendo n = B-A + 1, ho bisogno di ricavare la relazione di ricorrenza di questo algoritmo:
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]);
}
}
Aiuto?
Soluzione
Si assuma la complessità del vostro algoritmo ricorsivo è h(A,B)
.
Dal vostro codice è possibile dividere h
in 2 casi:
h(A,B) = { complexity-of-if-branch if A = B
{ complexity-of-rest-of-the-code otherwise
Il "ramo complessità-of-se-" è banale. Per "complessità-of-resto-of-the-code", in quanto si tratta recurringalgorithm
, è necessario includere di nuovo h
.
Ad esempio, se la funzione è definita come
function hh(A,B) {
for (var i = A+1; i < B; ++ i)
hh(i, B);
}
Poi la complessità sarà
hh(A,B) = hh(A+1, B) + hh(A+2, B) + ... + hh(B-1, B)
È possibile confrontare questa con il codice di generalizzare.
(a proposito, la complessità è h(A,B) = O(B * (B-A)!)
)
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow