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

מנהל: TA_Isana

שלח תגובה
shaishab
הודעות: 25
הצטרף: 19:32 26/10/2009

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

שליחה על ידי shaishab » 18:06 22/04/2010

מה זמן הריצה של קטע הקוד


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

igormi
הודעות: 7
הצטרף: 00:28 12/11/2009

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

שליחה על ידי igormi » 18:17 22/04/2010

נראה לי n*loglogn.

shaishab
הודעות: 25
הצטרף: 19:32 26/10/2009

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

שליחה על ידי shaishab » 18:23 22/04/2010

גם אני חושב ככה אבל רק להיות בטוח

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

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

שליחה על ידי michal cohen » 21:44 22/04/2010

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

igormi
הודעות: 7
הצטרף: 00:28 12/11/2009

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

שליחה על ידי igormi » 21:53 22/04/2010

לא הבנתי לאן נעלם הn בחזקה

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

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

שליחה על ידי michal cohen » 22:50 22/04/2010

הורדתי אותו בתוך הלוג...
ז"א:
log((logn)^n)= log(nlogn) xxxxxxx
תתעלם מה-X זה כדי שיראו את הסוגריים טוב

igormi
הודעות: 7
הצטרף: 00:28 12/11/2009

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

שליחה על ידי igormi » 22:58 22/04/2010

החזקה היא על הLOG ולא הn לכן אתה לא יכול לעשות מה שעשית.

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

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

שליחה על ידי michal cohen » 23:01 22/04/2010

צודק :)
תודה :)

שלח תגובה

חזור אל “- מבני נתונים 2010”