דף 1 מתוך 1

בוחן 2003

נשלח: 18:41 19/04/2010
על ידי lironsam
בחישוב זמן ריצה של התוכנית
A(n)
{
if (n  1)
return 0
else {
x f(n)
return ( A(n/3) + A(n/3) + x )
}
}

הגעתי למשוואה סופית של:
T(n)= 2T(n/3)+n logn+O(1)

O(1) השאלה האם אפשר להתעלם מה
או להקטין את הביטוי ע"מ לפשט אותו כדי שיתאים לשיטת האב?

ואם מקטינים ביטוי מה זה אומר מבחינת הביטוי הסופי של זמן הריצה ? (Ѳ \ O )

תודה

Re: בוחן 2003

נשלח: 18:46 19/04/2010
על ידי lironsam
ד"א נתון שזמן הריצה של (f(n הוא Ѳ(n logn)