ערכתי לאחרונה בתאריך 21.10.09 בשעה 16:07 בברכה, ronen333
אהלן חבר'ה :),
נשאלתי את השאלה הבאה:
"כתבו נוסחת T(N) המתארת את זמן הריצה של הפונקציה שכתבת, ופתרו אותה באמצעות שיטת האיטרציה".אפשר הסבר בבקשה איך אני מפעיל את שיטת האיטרציה על פונקציות רקוסביות? כי אני לא בטוח שהבנתי.
הפונקציה הרקורסיבית שלי היא:
void swap(int * a,int * b)
{
int temp=*a;
*a=*b;
*b=temp;
}
void recursive_selection_sort (int a, int n)
{
int max=a;
int i,index=0;
if(n==0)
return;
for(i=0;i<n;i++)
{
if(max<a)
{
max=a;
index=i;
}
}
swap(&a,&a);
recursive_selection_sort(a,n-1);
}
|
ורשמתי את הדבר הבא:
T(N)=T(N-1)+N+1T(N-1)=T(N-2)+N-1+1+N+1=T(N-2)+2N+1
T(N-2)=T(N-3)+N-2+1+2N+1=T(N-3)+3N+0
T(N-3)=T(N-4)+N-3+1+3N=T(N-4)+4N-2
T(N-4)=T(N-5)+N-4+1+4N-2=T(N-5)+5N-5
...
T(N-N)=0 T(N-K)=(K+1)N+N(N+1)/2
|
אין לי מושג אם אני עושה את זה כמו שצריך, ואם לא אשמח להסבר.
תודה רבה|כן|
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
