שאלה....

[d a y d r e a m e]

שאלה....

O(f) - O(f) = ? ?למה זה שווה​

 

[freak2100]

לדעתי

זה שווה ל

O(f)​

בסך הכל זה אותו סדר גודל... חוץ מזה, בסדרי גודל מתעלמים מהמקדמים, ז"א ש

O(f) ~ A*O(f)​

כשA קבוע, ואז אפשר להגיד ש

O(f) - O(f) ~ A*O(f) - B*O(f) ~ (A-B)*O(f)​

A-B גם כן קבוע ולכן זה שקול לסדר גודל של f(n... אבל זה הכל רק ניחושים, לא למדתי את הנושא הזה לעומק, רק כדרך אגב באיזה קורס מבוא...

 

[d a y d r e a m e]

אבל

O(f) מה עם תוצאות שליליות שיוצאות..? דוגמאות : נניח f=n^2 O(f) - O(f) = O(n^2) - O(n^2) = 2 - 5 = -3 < 0 O(f) - O(f) = O(n^2) - O(n^2) = n - (n+2) = -2 < 0 O(f) - O(f) = O(n^2) - O(n^2) = n^2+n+1 - (n^2+n+7) = -6 < 0 O(f) - O(f) = O(n^2) - O(n^2) = 3 - (n^2+8) = -n^2-5 O , טטא , אומגה מוגדרים רק על פונקציות אי שליליות אז אין אפשרות לסמן את השליליים כאות מסויימת. אז איך מסמנים את התחום הנרחב הזה ?​

 

[freak2100]

שוב, לא למדתי את התחום הזה לעומק, אבל לדעתי

ההגדרה של

O(f)​

היא

lim(O(f)/f) = 0​

lim הוא כש n->אינסוף... אז אפשר לבדוק:

lim( (O(f)-O(f))/f )​

ומשימוש באריתמתיקה של גבולות זה גם יוצא 0, ולכן

O(f) - O(f) ~ O(f)​

זאת דעתי, יכול מאוד להיות שאני טועה...

 

[freak2100]

בעצם, אני לא בטוח שההגדרה שלי נכונה...

יכול להיות שההגדרה שלי ל

O(f)​

היא הגדרה של משהו אחר... מממ... נדמה לי שזה

o(f)​

ושההגדרה הנכונה היא

lim (O(f)/f) = 1​

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

 

[freak2100]

עכשיו, כשאני חושב על זה עוד קצת...

לא יודע בדיוק מה לחפש בויקיפדיה, אבל לדעתי... ההגדרה של O היא שO(f(n קטנה בסדר גודל מf(n, וזה אומר ש:

lim(O(f)/f) <= 1​

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

 

[freak2100]

או, הנה, מצאתי בויקיפדיה...

http://en.wikipedia.org/wiki/Big_O_notation טוב, מסתבר שההגדרות שלי לא נכונות

 

[johnny d]

זה לא שווה לשום דבר,

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