שיחה:88-280 תשעג סמסטר א

חזרה לדף הקורס

גלול לתחתית העמוד

הוספת שאלה חדשה

הוסף שאלה חדשה (רשום כותרת לשאלה, רשום את תוכן השאלה ולחץ על שמירה למטה מימין לסיום).

-עזרה על עיצוב הטקסט וכתיב מתמטי תוכלו למצוא כאן

אם אתם רוצים לשאול שאלה עליכם ליצור חשבון משתמש באתר.

שאלות

תרגיל 1

עד כמה צריך לפרט בהוכחת קצבי הגידול (האם ניתן להשתמש בגבולות שהוכחנו באינפי לפני שנתיים?)

תשובה:

אפשר פשוט להשתמש בהגדרה:

[math]\displaystyle{ f(n)=o(g(n)) }[/math] (סימון אחר [math]\displaystyle{ f(n)\ll g(n) }[/math]) אם [math]\displaystyle{ \lim_{n\to\infty}\left|\frac{f(n)}{g(n)}\right|=0 }[/math].

(כלומר g גדלה מהר יותר מ-f)

וככה לדרג את כל הפונקציות

תרגיל 1 שאלה 4

נראה לי שיש טעות באלגוריתם. בשורה: return j, זה צריך להיות לדעתי return i. כמו שזה עכשיו הוא תמיד יחזיר את אותו הערך, את n.
אגב, קצת פחות חשוב, אבל צריך להיות רשום A[j]==i במקום a[j]==i

תשובה: נכון, זה צריך להיות return i. אני מעלה מחדש את קובץ התרגיל עם התיקון. תודה

שאלה 1 פונקציה 1

[math]\displaystyle{ e^{\log_d n^3} = e^{3\log_d n} = e^{3\frac{\log_e n}{\log_e d}} = n^{\frac{3}{\log_e d}} }[/math] מדוע במקרה זה לא חשוב לדעת את הבסיס של הלוגריתם?

לדוגמא, במידה ו [math]\displaystyle{ d=\sqrt[100]{e} }[/math] אז הפונקציה שייכת ל: [math]\displaystyle{ O(n^{300}) }[/math] ואילו אם [math]\displaystyle{ d=e^3 }[/math] אז הפונקציה שייכת ל: [math]\displaystyle{ O(n) }[/math]
וזה משפיע כמובן על היחס של קצב הגידול שלה לעומת פונקציה 2 לדוגמא.

תשובה: נכון

בסיס הלוגריתם אינו משנה רק כאשר מדובר בלוגריתם רגיל או לוגריתם בחזקה כלשהי.

אך כאשר מדובר בלוגריתם באקספוננט זה זה כן משנה.

אז איך אני אמור לדרג את הפונקציה הזאת לעומת פונקציות 2,6 או 8 כשהבסיס אינו ידוע?