שיחה: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 כשהבסיס אינו ידוע?