דף 1 מתוך 1

שאלה 4 בבוחן 2003 קיץ

נשלח: 18:06 22/04/2010
על ידי shaishab
מה זמן הריצה של קטע הקוד


x ==0
for ( i = 1 ; i <=(log n)^n ; i = 2*i )
+1x = x

Re: שאלה 4 בבוחן 2003 קיץ

נשלח: 18:17 22/04/2010
על ידי igormi
נראה לי n*loglogn.

Re: שאלה 4 בבוחן 2003 קיץ

נשלח: 18:23 22/04/2010
על ידי shaishab
גם אני חושב ככה אבל רק להיות בטוח

Re: שאלה 4 בבוחן 2003 קיץ

נשלח: 21:44 22/04/2010
על ידי michal cohen
זה לא יוצא O(logn)?
כי הרי עבור k איטרציות נקבל שהקוד רץ עד ש-2 בחזקת K שווה ל-לוג אן בחזקת אן.
אז מוציאים לוג על שני האגפים ומקבלים ש-K שווה ל:
log(nlogn)
שזה בעצם logn+loglogn שזה או של לוג אן...
לא?

Re: שאלה 4 בבוחן 2003 קיץ

נשלח: 21:53 22/04/2010
על ידי igormi
לא הבנתי לאן נעלם הn בחזקה

Re: שאלה 4 בבוחן 2003 קיץ

נשלח: 22:50 22/04/2010
על ידי michal cohen
הורדתי אותו בתוך הלוג...
ז"א:
log((logn)^n)= log(nlogn) xxxxxxx
תתעלם מה-X זה כדי שיראו את הסוגריים טוב

Re: שאלה 4 בבוחן 2003 קיץ

נשלח: 22:58 22/04/2010
על ידי igormi
החזקה היא על הLOG ולא הn לכן אתה לא יכול לעשות מה שעשית.

Re: שאלה 4 בבוחן 2003 קיץ

נשלח: 23:01 22/04/2010
על ידי michal cohen
צודק :)
תודה :)