מבנה נתונים: שאלה

[shochat1]

מבנה נתונים: שאלה

האם הזהויות הבאות נכונות:

O(f(x))-O(f(x))=c (?) O(f(x))+O(g(x))=max{f(x),g(x)}​

במידה ומה שרשמתי נכון למה זה נכון ??

 

[vinney]

נתתי לך הגדרה של המושגים

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

 

[shochat1]

האמת לא מבין איך

ההגדרה שרשמת לי O - פונקציה F היא O של G אם G זאת כפולה של F במקדם סופי כלשהו. עוזרת לי לפתור את הזהות הרי O של F מהווה חסם הדוק של הפונקציה F ואני לא מבין איך זה עוזר לי פה. לאחד או לשני הזהויות האלה אולי הזהות ה1 = O(1) ו2 היא O(fg)1 אבל גם אם כן לא הבנתי למה ??

 

[vinney]

O זה לא חסם הדוק

חסם הדוק זה תתה. O של משהו זה בהחלט לא המשהו הזה, להגיד O(1)=1 זה לא נכון בעליל (כמו גם להגיד ש O(f)=f זה לא נכון באותה מידה, זה לגבי הזהות הראשונה).

 

[shochat1]

אוקיי נכון

O גדולה הוא חסם הדוק עליון ככה שהוא גדול שווה מF ולא התכוונתי שO של משהו שווה למשהו הזה אלה שווה לחסם הדוק עליון של המשהו המדובר פשוט טעיתי בכיתוב ...

 

[vinney]

O זה לא חסם הדוק

זה חסם עליון, זה נכון, אבל הוא לא חייב להיות הדוק.

 

[gil levi]

תיקון קל.

קודם כל צריך לזכור ש O(f) zzz זו קבוצה ולכן הביטוי f=O(f) zzz פשוט לא נכון. לעומת זאת, כן מתקיים ש f∈O(f) zzz. אותו דבר נכון עבור טטה ועבור אומגה. השימוש ב= במקום ∋ מעט מבלבל.

 

[vinney]

../images/Emo45.gif

 

[gil levi]

אני לא מבין בכלל.

O(f) zzz היא קבוצה. איך אתה מגדיר בדיוק חיבור וחיסור בין O של דברים?

 

[ron369]

בעזרת נציגים?

 

[ron369]

או כך:

{f | קיימים g,h כך ש f=g+h}

 

[gil levi]

אוקיי. תודה.

אני מחכה לאישור של shochat1 שזה אכן מה שהוא התכוון אליו (זו פעם ראשונה שאני רואה את ההגדרה הזו אז אני מניח שלא בטוח שזה משהו "ידוע" וייתכן שshochat1 הגדיר זאת אחרת).

 

[ron369]

אחרי מבנים אלגבריים, הגדרות כאלו

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

)

 

[shochat1]

זה נכון

ע"פ ההגדרה שרשומה בויקיפדיה אבל השאלה מה הנימוק שרושמים לדברים האלה

 

[shochat1]

מישהו ?

 

[vinney]

תחשוב על זה כך

יש לך ביטוי כזה:

O(f) - O(f)​

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

 

[shochat1]

או גדול של 1 כי

זה מהווה קונסט בניגוד למשתנה...אבל איך נסביר למשל ערבוב של פעולות עם O(g)כמו כפול או חיבור הרי אנו יודעים:

O(f(x))*O(g(x))=O(f*g) O(f(x))-O(g(x))=O{max(f,g}​

הבעיה שלי שאני לא יודע להסביר למה זה שווה לזה ??

 

[vinney]

תלך לפי ההגדרה

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

 

[gil levi]

לגבי השניה.

דבר ראשון, אני מניח שהתכוונת ל

O(max(f, g})​

ואם לא, אז תסביר לי למה בדיוק התכוונת. כמו כן:

O(f + O (g = {h| h=f' + g', f'∈O(f),g'∈O(g) }​

ואם לא, אז תסביר לי למה בדיוק התכוונת. נסמן:

m = max{f, g}​

ונשים לב שלכל n:

➀f≤m ➁g≤m​

תהי h zzz ב O(f) + O(g) zzz. ברור ש m שהגדרו מקודם שייכת ל O(max(f,g)zz. כדי להראות ש:

O(f + O(g) = O(max{f, g}​

צריך להראות שיש קבוע C<0 ומספר טבעי N0 כך ש:

C*m ≥ h​

לכל n>N0. מפה נסה להמשיך לבד. תשתמש באי-שיוויונים 1 ו 2. אם תתקשה, אשמח לעזור.

 

[shochat1]

תודה עוד שאלה חשובה

איך מכריעים לגבי מקרים גרוע ממוצע וטוב של O, o w ותטא אני מבין את צורת הגרפים של כל אחד וההגדרות שלהם O - גדול שווה o- גדול W (אומגה גדולה)- קטן שווה w אומגה קטנה) - קטן תטא - היא מעין שילוב של או גדולה וW