משתמש:Ddd/mvn1

מתוך ויקיפדיה, האנציקלופדיה החופשית

2א:לא נכון- שתי פונקציות לדוגמא:g(n)=n^2, ואם f(n-1) < n \, אז f(n)=n^3 אחרת f(n)=f(n-1) \,נוכיח ש. f(n) \ne O (g(n)) \,:לכל c,ולכל \, n_0 שנבחר, קיים \, n>n_0 בו n^3 > c \cdot n^2 \,כי לכל n^3 תמיד יהיה n שיהיה גדול ממנו, ואז n^3 של ה n הזה יהיה גדול מספיק. נוכיח ש f(n) \ne \Omega (g(n)) \,:ב"מרווחים" בין הקפיצה ל n^3 עד ש f(n-1)<n הפונקציה שווה לקבוע כאשר לכל n יהיו אינסוף מרווחים עם n גדול יותר. כאשר ב "קצה" המרווח f(n)=n וזה בוודאי לא באומגה של g(n)=n^2

ב:נכון-נניח שלא מתקיים \Omega_{\infty}כלומר מס' הנקודות הוא סופי לכל с. לכן קיימת הנקודה שבה n הוא הגדול ביותר מבין הנקודות. נקרא לה n_1 \, הנקודה הנ"ל תלויה ב с.נבחר C מסוים C_0 \,. עבורו לכל n>n_1 \,מתקיים:f(n)<c_0 \cdot g(n) \, וזה מקיים לפי ההגדרה את f(n)=O(g(n)) \,

ג:נכון- צריך להוכיח:עבור כל c>0 קיים n_0 \, כך שעבור כל n>n_0 \, מתקיים n^{\epsilon}\ge c \cdot log^k(n)הזזת אגפים:\frac{n^{\epsilon}}{log^k (n)} \ge c אבל ידוע שלכל a,b>0 lim_{x \rightarrow \infty} \frac{x^a}{ln^b(x)}=0 לכן, ע"פ הגדרת הגבול, לכל קבוע C קיים n>0 כך שהתנאי מתקיים. מש"ל

ד.נכון-הפונקציה f(x)=\frac{1}{x} ע"פ ההגדרה קיים C=1 ו n_0=1 \, ואכן, בתחום הזה \frac{1}{sqrt(x)} \ge \frac{1}{x}

ה.לא נכון-נניח בשלילה שזה נכון,log*(log(n))=log*(n)-1 \,לפי ההגדרה(כי צריך לעשות לוג פעם אחת פחות. צריך להוכיח: קיימים \, C,n_0 כך ש log^*(n)-1 \le c \cdot log(log^*(n))העברת אגפים:\frac{log^*(n)}{log(log^*(n))}-\frac{1}{log(log^*(n))} \le c אבל כאשר n שואף לאינסוף, החלק הראשון בביטוי השמאלי שואף לאינסוף(ע"פ הגבול בסעיף ג) והחלק השני שואף לאפס כי המכנה שואף לאינסוף. לכן זה יהיה גדול מכל קבוע, ולכן זה לא נכון.

ו.לא נכון-ע"פ נוסחת סטירלינג, log(n!) \cong n log (n)-n בנוסף [log(n)]!=e^{log([log(n)]!)} \cong e^{log(n) \cdot log(log(n))-log(n)}=\frac{n^{log(log n)}}{n} המשך הפיתוח: n^{log(log n)-1} \,ומכיוון שקיים n עבורו log(log(n))-1 > 2 \, זה לא יכול להיות ב O(n log(n)-n) \, כי חזקת n גדולה יותר.

ז.נכון-כפי שהראיתי, ב[log(n)]! \, (מעבר ל n מסוים) חזקת n גדולה מאשר ב log(n!) ולכן ע"פ ההגדרה (אם נבחר למשל כ \, n_0 אם המספר שעבורו log(log(n))-1 \ge 2 אז מכיוון ש nlog(n)=log(n^n) \ge log(n!) מתקיים:n^{log(log(n))-1} \ge nlog(n) \ge log(n!)

ח.לא נכון-ע"פ ההגדרה, לכל C קיים \, n_0 כך שעבור כל \, n>n_0 מתקיים 1 \le c \cdot f(n). ע"פ הטענה (f(n))^2=O(f(n)) \,כלומר קיימים \, c_1 ,n_1 כך שעבור כל \, n>n_1 מתקיים (f(n))^2 \le c_1 f(n)אבל אם נבחר \, c_2 >c_1 ע"פ הנתון קיים \, n_0 שלכל n גדול ממנו f(n) \ge c_2ואם נכפול את שני הצדדים ב f(n) נקבל (f(n))^2 \ge c_2 f(n) > c_1 f(n) וזה סותר את הטענה, ולכן היא לא נכונה