מבני נתונים - עזרה בש"ב

[molecules]

מבני נתונים - עזרה בש"ב

נתון קטע הקוד הבא:

int i,j for j=1, j<=n, ++j { y=j while y < n y*=2; }​

מהו זמן הריצה של הלולאה הפנימית? לי יוצא משהו לא הגיוני: LOG N/J תודה רבה

 

[johnny d]

theta of J*lg N

אפשר להראות ע"י חישוב ישיר של סכום כל האיטרציות של הלולאה החיצונית.

 

[molecules]

תוכל בבקשה לפרט איך הגעת לזה?

אני בניתי משוואה שאומרת כי עבור J כלשהו מס' הפעמים שמתבצעת עבורו הלולאה הפנימית הוא: j*2^x = n ע"י הפעלת LOG על כ"א מהאגפים אני מקבל את התוצאה LOG [N/J] = X. תוכל אולי בבקשה להסביר לי איפה אני טועה? תודה, נ.ב אני לא בטוח בזה אבל התשובה הסופית לכל קטע הקוד אמורה להיות theta of nlogn

 

[amirxbox]

אתה לא יכול לתת תשובה סופית עם J

דרך אגב השאלה מאוד מוכרת לי יש מצב שאתה מבן גוריון? אם כן אז יש לי את התשובה איפהשהו

 

[amirxbox]

פתרון:

תפעל לפי מה שאותנו לימדו לפחות: שורה ראשונה תרשום את כל ה J ים האפשריים

1 2 3 4 5 6 7 .... n מתחת לכל J תרשון כמה תתבצע הפעולה שבWHILE. LOGN LOG(N-1)... LOG1​

ועכשיו תחבר את הלוגים האלו יוצא

log(n!)​

וכידוע התשובה היא מאותו סדר גודל של טטה של nlogn

 

[molecules]

כן הבנתי איך זה עובד - תודה רבה

 

[molecules]

לא אני מת"א-יפו

התשובה שלי היא לא עם J, התייחסתי שם רק ללולאה הפנימית. התשובה הסופית שלי יוצאת לא הגיונית כ"כ: nlogn-logn! which is ridicules