ויקיספר

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה: הבדלים בין גרסאות בדף

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Atavory (שיחה | תרומות)
7,521 עריכות
Atavory (שיחה | תרומות)
7,521 עריכות
ביטול גרסה 53328 של Thedsadude (שיחה)
שורה 84:
}}
 
g(n)</math> עבור===הקבוצה <math dir = "ltr">\displaystyle c > 0\Theta</math> כלשהו.===▼
הקבוצה <math dir = "ltr">\displaystyle O(g(n))</math> הנה קבוצת כל הפונקציות <math dir = "ltr">\displaystyle f(n)</math> כך ש<math dir = "ltr">\displaystyle f(n)</math>, עבור <math dir = "ltr">\displaystyle n</math> גדול מספיק, חסומה מלמעלה ע"י <math dir = "ltr">\displaystyle c \cdot▼
▲g(n)</math> עבור <math dir = "ltr">\displaystyle c > 0</math> כלשהו.
 
▲הקבוצה <math dir = "ltr">\displaystyle O\Theta(g(n))</math> הנה קבוצת כל הפונקציותהחיתוך של<math dir = "ltr">\displaystyle fO(g(n))</math> כך שו<math dir = "ltr">\displaystyle f\Omega(g(n))</math>, עבור <math dir = "ltr">\displaystyle n</math> גדול מספיק, חסומה מלמעלה ע"י <math dir = "ltr">\displaystyle c \cdot.
{{הגדרה|תוכן =
<math dir = "ltr">\displaystyle O\Theta(g(n)) = \{fO(g(n) |) \exists_{cbigcap > 0, n_0>0}\forall_{n \ge n_0}fOmega(g(n) \le c \cdot)</math>}}
g(n)\}</math>}}
 
[[תמונה:theta intuition.png|מרכז|100%|אינטואיציה לתטא.]]▼
 
[[תמונה:DSA O intuition.png|מרכז|100%|אינטואיציה לאו.]]
 
{{הגדרהדוגמה|תוכן = ▼
בהינתן פונקציה
הקבוצה <math dir = "ltr">\displaystyle \Theta(gf(n))</math>כלשהי, הנההאם החיתוך של<math dir = "ltr">\displaystyle O(gf(n))</math>שייכת ול<math dir = "ltr">\displaystyle \OmegaTheta(gf(n))</math>.? ▼
כן, משום שעבור <math dir = "ltr">\displaystyle n \ge 1</math>,‏ <math dir = "ltr">\displaystyle f(n) \ge f(n)</math>, ולכן <math dir = "ltr">\displaystyle f(n) = O(f(n))</math>; מצד שני, עבור <math dir = "ltr">\displaystyle n \ge 1</math>,‏ <math dir = "ltr">\displaystyle f(n) \le f(n)</math>, ולכן <math dir = "ltr">\displaystyle f(n) = \Omega(f(n))</math>. כפי שראינו מקודם, כותבים זאת <math dir = "ltr">\displaystyle f(n) = \Theta(f(n))</math>.
}}
 
{{הערה|1 =
'''הסבר אינטואיטיבי''': <math dir = "ltr">\displaystyle f(n)</math> מתנהגת, ב<math dir = "ltr">\displaystyle n</math>-ים גדולים, כקטנה או שווה עד כדי קבוע מ<math dir = "ltr">\displaystyle g(n)</math>.
בראותך <math dir = "ltr">\displaystyle \Theta(g(n))</math>, עליך להסיק מההקשר האם מדובר בקבוצה או באיבר.}}
 
 
הקבוצה <math dir = "ltr">\displaystyle \Omega(g(n))</math> הנה קבוצת כל הפונקציות <math dir = "ltr">\displaystyle f(n)</math> כך שכל
פונקציה <math dir = "ltr">\displaystyle f(n)</math>, עבור <math dir = "ltr">\displaystyle n</math> גדול מספיק, חסומה מלמטה ע"י
<math dir = "ltr">\displaystyle c \cdot g(n)</math>, עבור <math dir = "ltr">\displaystyle c > 0</math> כלשהו.
 
▲{{הגדרה|תוכן =
<math dir = "ltr">\displaystyle \Omega(g(n)) = \{f(n) | \exists_{n_0>0, c > 0}\forall _{n \ge n_0}f(n) \ge c
\cdot g(n)\}</math>}}
 
 
[[תמונה:Dsa Omega intuition.png|מרכז|100%|אינטואיציה לאומגה.]]
 
'''הסבר אינטואיטיבי''': <math dir = "ltr">\displaystyle f(n)</math> מתנהגת, ב<math dir = "ltr">\displaystyle n</math>-ים גדולים, כגדולה או שווה עד כדי קבוע מ<math dir = "ltr">\displaystyle g(n)</math>.
 
 
▲הקבוצה <math dir = "ltr">\displaystyle \Theta(g(n))</math> הנה החיתוך של<math dir = "ltr">\displaystyle O(g(n))</math> ו<math dir = "ltr">\displaystyle \Omega(g(n))</math>.
 
{{הגדרה|תוכן = ▼
<math dir = "ltr">\displaystyle \Theta(g(n)) = O(g(n)) \bigcap \Omega(g(n))</math>}}
 
 
▲[[תמונה:theta intuition.png|מרכז|100%|אינטואיציה לתטא.]]
 
▲{{הגדרהדוגמה|תוכן =
'''הסבר#האם אינטואיטיבי''':מציאת איבר במקרה הגרוע בחיפוש ליניארי הנה <math dir = "ltr">\displaystyle f\Theta(n)</math>? מתנהגת,כן משום שהיא ב<math dir = "ltr">\displaystyle O(n)</math>-ים גדולים,וגם כ<math dir = "ltr">\displaystyle g\Omega(n)</math>.▼
#האם יש הבדל בין <math dir = "ltr">\displaystyle O(1)</math>לבין <math dir = "ltr">\displaystyle \Omega(1)</math>? לא. אם משהו הוא <math dir = "ltr">\displaystyle \Theta(1)</math>, אז עפ"י ההגדרה הוא גם <math dir = "ltr">\displaystyle O(1)</math>. אבל גם אם נאמר לנו רק שהוא <math dir = "ltr">\displaystyle O(1)</math>אנחנו יודעים שהוא <math dir = "ltr">\displaystyle \Theta(1)</math>, משום שכל דבר (שנראה בקורס) הוא <math dir = "ltr">\displaystyle \Omega(1)</math>.}}
 
{{הארה|1 =
▲'''הסבר אינטואיטיבי''': <math dir = "ltr">\displaystyle f(n)</math> מתנהגת, ב<math dir = "ltr">\displaystyle n</math>-ים גדולים, כ<math dir = "ltr">\displaystyle g(n)</math>.
נתן לראות שיש שתי דרכים לסימון קבוע חיובי כלשהו: <math dir = "ltr">\displaystyle O(1)</math> וכן <math dir = "ltr">\displaystyle \Theta(1)</math>- משעותם זהה. לרוב משתמשים ב<math dir = "ltr">\displaystyle O(1)</math>לצורך כך.
}}
 
==כללי סדרי גדילה==
אוחזר מתוך "https://he.wikibooks.org/wiki/מבני_נתונים_ואלגוריתמים_-_מחברת_קורס/אלגוריתמים/סדרי_גדילה"