تجد علاقة تكرار هذه الخوارزمية؟
-
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)
.
من الكود الخاص بك يمكنك الانقسام h
في حالتين:
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)!)
)
لا تنتمي إلى StackOverflow