אני שואל לגבי הוכחת O לדוגמא

לפי ההגדרה אם 1 הוא חסם עליון של 2

אז נחפש קבועים n0 ו c , כמובן שניהם גדולים מ 0 ,(n0 מספרים שלמים ו c כמובן שלא) שהחל מ n שגדול מ n0 אז

1 כפול c גדול שווה מ 2-זו ההגדרה ,

ברור לי למה זה החל מn0 מסויים,כי מדבאים באינסוף ורוצים ששם יהיה חסם עליון,שהחל ממספר מסויים עד אינסוף הוא חסם עליון שלו

אבל מה ה c מייצג? למה צריך אותו בהגדרה?

(ברור לדוגמא שאם ה c חוסם את ה n0 זו סתירה)

אבל מה ההיגיון בלהכפיל מ c

יותר מכך,

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

אבל כשמוכיחים o (קטן) צריך לכל c

למה?

יש לי כיוון אבל לא מוברר

תודה

כי ככה למשל תקבל ש2N שייכת לO של N

בסופו של דבר שמדברים על שאיפה לאינסוף הכפלה בסקלר כלשהי כבר לא ממש חשובה

בנוסף, זה מאוד מפשט חישובי סיבוכיות של אלגוריתמים כי אין צורך לחשב פעולות בודדות ולהכפיל בN אלא פשוט הכל נכנס תחת ה גג של O של 1

אגב, O זה רק אחד משלושת הסימונים. יש גם THETA OMEGA שביחד מכסים את כל האפשרויות להבדלים בין פונקציות

הקטע בסיבוכיות זה שבשאיפה לאין סוף לקבוע אין מהות לקבוע לעומת המשתנה. למשל 10000N קטן יותר מN^2 כאשר N שואף לאינסוף (ולמעשה החל מN=10000).

החלק החשוב בסיבוכיות זה לחשב את הבעיה העומדת בפניך, לפי אמות המידה המקובלות. למשל אצלי בטכניון יש לך שורש (כל סוגי השורשים), לוג לפי בסיס 2 של N, כל החזקות, 2 בגובה N, וN עצרת ואת כל המכפלות בין מה שאמרתי.

עליך למצוא את זאת שבאין סוף תיהיה הקרובה ביותר.