שאלה בסיבוכיות

[chalucha]

שאלה בסיבוכיות

היי,
אני צריך להוכיח ש (n + a)^b = θ(n^b) לכל קבוע a,b כאשר b>0
ניסיתי לפתח את זה עם הבינום אבל זה לא נותן כלום.
למישהו יש אולי רעיון אחר ?

תודה!

 

[Shimsoni]

תפתח את נוסחאת הבינום

 

[Guy Yafe]

האמת היא שהתשובה היא באמצעות בינום

לאחר שתפתח את נוסחת הבינום תראה שיש איבר מוביל n^b וכל שאר האיברים הם עם חזקה קטנה מ - b.
אם אתה כבר יודע להוכיח שכולם הם theta(n^b) z, ואם אתה יודע להוכיח שסכום של איברים הולך כמו האיבר הגדול ביותר, יש לך את ההוכחה ביד.

 

[vinney]

לי עוזר ללכת בדרך השלילה כשבדרך הישרה זה לא

עובד.

פיתחת את הבינום, עכשיו תניח שהטענה לא נכונה ותראה איפה תתקע. אתה חייב להתקע איפשהו.

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

 

[טרול המתכנן]

סע להגדרה, תכניס הכל מתחת לחזקה

הגבול יצא לך משהו ממשפחת ה-e (בגובה משהו).
זה כל מה שאתה צריך להוכיח (שהגבול סופי וחיובי).

 

[chalucha]

תודה! הבנתי את הבינום. האם ניתן גם בדרך

הבאה להוכיח?
חשבתי להוציא n מחוץ לסוגריים , כך שיש לי:
N^b(1+a\N)^b ואז למצוא C1,C2 ו N0 עבורם
c1*n^b <= N^b(1+a\N)^b <= c2*n^b

תודה

 

[ArchiParchi]

דרך יותר קלה מהבינום

מכיוון שמדובר בתטא צריך להראות גם אומגה וגם O.
החלק של האומגה קל מאוד, פשוט הביטוי מצד שמאל גדול מסתם n^b לכל n גדול מ-0 (אם a חיובי, אם לא פשוט תגיד שזה קטן מ n/2 החל מ...)
החלק של O גם לא קשה, במקום n+a תכתוב 2n שזה גדול יותר החל מ-n מסוים (משוואה פשוטה להראות מאיזה n זה מתקיים כתלות ב-a) וקבלת 2 בחזקת b כפול n בחזקת b וזה קבוע כפול n^b ולכל מש"ל.