סדרי גודל של אלגוריתם

[amir y]

סדרי גודל של אלגוריתם

אני צריך למצוא מה הערך של:

O(f(x)) - O(g(x)) = ?​

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

 

[ChipsMan]

אממ..

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

 

[M00sad]

מבחנה מתמטית מהו ערך הביטוי../images/Emo35.gif

 

[M00sad]

../images/Emo105.gif

שכחתי להקפיץ

 

[ChipsMan]

ערך הביטוי הוא קבוצה..

מכייון ש-O מוגדר להיות קבוצה (אל תשכח את זה

) אז גם הפרש של קבוצות הוא קבוצה (לפחות זה מה שלמדתי במתמטיקה דיסקרטית

)

 

[amir y]

ממש מלמטה?

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

 

[ChipsMan]

אממ..

סדר גודל של (f(x היא קבוצה של כל הפונקציות שקבוע כפול (f(x חוסם אותן מלמעלה החל מ-x0 מסויים. סדר גודל של (g(x היא קבוצה של כל הפונקציות שקבוע כפול (g(x חוסם אותן מלמעלה החל מ-x0 מסויים. בהנתן שתי קבוצות A,B, ההפרש A-B (מסומן גם על ידי A\B) מוגדר להיות כל האיברים שנמצאים ב-A ולא נמצאים ב-B. ולכן הביטוי:

O(f(x)) - O(g(x))​

הוא כל הפונקציות ששייכות לסדר גודל של (f(x ולא שייכות לסדר גודל של (g(x. תסיק מכאן את המסקנות.

 

[amir y]

אממ.. 2 ../images/Emo13.gif

תודה. עוד שאלה קטנה, מה אם סדר הגודל של f(x) קטן מזה של g? יש איזושהי מוסכמה ש f גדולה מ g?

 

[ChipsMan]

שום מוסכמה ../images/Emo13.gif

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

 

[amir y]

טופ...

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

 

[ChipsMan]

זה מאד הגיוני..

זה רק חסר כל שימוש פרטקי, חוץ מלגרום לך להזכר מה זה הפרש בין שתי קבוצות

 

[עידו123456]

אממ...

הפרש מגדר בכל מקרה, אבל A\B שונה מ B\A... במקרה ש (g(x גדול מ (f(x אזי (f(x)-g(x הינו הקבוצה הריקה ו- O של הקבוצה הריקה אינו דבר קיים (אלא אם כן מגדירים את זה להיות (O(1 ) אם (g(x קטן מ (f(x אזי (f(x)-g(x הינו אכן התחום שהוא ((O(f(x ואומגה של (g(x. במקרה שהם שווים אזי שוב הגענו לקבוצה הריקה.

 

[ChipsMan]

אף פעם לא אמרתי שהם זהים..

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

 

[עידו123456]

טוב ../images/Emo13.gif

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