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

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


כדאי לדעת:

בספר הקורס, הפרקים "Growth of Functions" ו"Summations" דנים בנושאים אלה.

הפונקציות בהן נעסוק

עריכה

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

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

קבוצות סדרי הגדילה

עריכה

הקבוצה  

עריכה
 

כדאי לדעת:

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


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

הגדרה:

 

 
אינטואיציה לאו.




דוגמה:

  1. האם (הפונקציה)   שייכת לקבוצה  ? כן, מפני שעבור  ,‏  .
  2. האם   שייכת ל ? כן, מפני שעבור  ,‏  .


 

כדאי לדעת:

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




דוגמה:

האם  שייכת ל ? לא. נניח בשלילה שקיימים קבועים  , כך שמתקיים  . אז  , שאינו נכון.


למרבה הצער, הסימון   משמש לשני דברים שונים: הקבוצה  , או איבר מהקבוצה  . שלוש הדוגמאות שראינו מסומנות בד"כ כ , ‏ , ו .


 

שימו לב:

בראותך את הסימון  , עליך להבין מההקשר האם מדובר אכן בקבוצה או באיבר מתוך הקבוצה.



דוגמה:

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


הקבוצה  

עריכה
 

כדאי לדעת:

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

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

הגדרה:

 

 
אינטואיציה לאומגה.




דוגמה:

  1. האם  שייכת ל ? כן, מפני שעבור  ,  .
  2. האם   שייכת ל ? כן, משום שעבור  ,‏  .
  3. האם  שייכת ל ? כן, משום שעבור  ,‏  .


בדיוק כמו ב , גם   משמשת לשני דברים: הקבוצה  , או איבר הקבוצה  . שלוש הדוגמאות הקודמות נכתבות בד"כ כ ,‏  , ‏ ו .


 

שימו לב:

בראותך  , עליך להסיק מההקשר האם מדובר בקבוצה או באיבר מהקבוצה.



דוגמה:

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




דוגמה:

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


הקבוצה  

עריכה
 

כדאי לדעת:

אינטואיטיבית, הקבוצה   כוללת את הפונקציות שקצב הגדילה שלהן הוא זה של  .

הקבוצה   הנה החיתוך של  ו .

הגדרה:

 

 
אינטואיציה לתטא.




דוגמה:

בהינתן פונקציה  כלשהי, האם  שייכת ל ? כן, משום שעבור  ,‏  , ולכן  ; מצד שני, עבור  ,‏  , ולכן  . כפי שראינו מקודם, כותבים זאת  .


 

שימו לב:

בראותך  , עליך להסיק מההקשר האם מדובר בקבוצה או באיבר.



דוגמה:

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


 

כדאי לדעת:

ניתן לראות שיש שתי דרכים לסימון קבוע חיובי כלשהו:   וכן  - משמעותם זהה. לרוב משתמשים ב לצורך כך.

כללי סדרי גדילה

עריכה

רפלקסיביות

עריכה

משפט:

לכל  :

  1.  
  2.  
  3.  

(כבר הוכחנו זאת.)

אדיטיביות

עריכה

משפט:

לכל  :

  1.  
  2.  
  3.  


 

כדאי לדעת:

הכלל הראשון, לדוגמה, אומר שאם  וכן  , אז  .


הוכחה: (1)

עפ"י ההגדרה:

  •   משמעו שלכל  ,‏  ,‏ עבור   כלשהם.
  •   משמעו שלכל  ,‏  ,‏ עבור   כלשהם.

לכן:

  • לכל  ,‏  .
  • לכל  ,‏  .

מקבלים את התוצאה ע"י חיבור שני האי-שוויונים האחרונים.

 

סימטריה הפכית

עריכה

משפט:

לכל  ,‏  .


הוכחה:  


 
 
 
 
 

 

טרנזיטיביות

עריכה

משפט:

לכל  :

  1.  
  2.  
  3.  


הוכחה: דומה למה שראינו באדיטיביות.

 

שימוש בגבולות

עריכה

משפט:

לכל  ,‏ אם   קיים, ו , אז:

  1.  
  2.  
  3.  


הוכחה: (1)

 
 
 
 
 

 


 

שימו לב:

ייתכן ש ,‏  , או  , אך הגבול פשוט אינו קיים.


 

עכשיו תורכם:

מה ההשלכות של כלל הגבול על פולינומים? בצורה אחרת, אם

 , ו  , אז מה קובע את סדר הגדילה בין   ו ?


פתרון

לפי כלל הגבול, נוכל לקבוע את הדברים הבאים:

  1. אם  , אז  .
  2. אם  , אז  .
  3. אם  , אז  .


דמיון לאופרטורי השוואה

עריכה

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

הקבוצה   והייחס  

עריכה

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

ראשית, נשים לב שמתקיים   (למה?).

יש עוד נקודות דמיון. בין היתר:

  • רפלקסיביות: לכל פונקציה   מתקיים  , ובאותו אופן, מתקיים  .
  • טרנזיטיביות: לכל   מתקיים   ,ובאותו אופן,  

הקבוצה   והייחס  

עריכה

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

ראשית, נשים לב שמתקיים   (למה?).

יש עוד נקודות דמיון. בין היתר:

  • רפלקסיביות: לכל פונקציה   מתקיים  , ובאותו אופן, מתקיים  .
  • טרנזיטיביות: לכל   מתקיים   ,ובאותו אופן,  

הקבוצה   והייחס  

עריכה

הקביעה   אומרת ש  שווה ל . הקביעה   אומרת שקצב הגדילה של  שווה לקצב הגידול של  . יש דמיון כלשהו בין שתי הקביעות.

ראשית, נשים לב שמתקיים   (למה?).

יש עוד נקודות דמיון. בין היתר:

  • רפלקסיביות: לכל פונקציה   מתקיים  , ובאותו אופן, מתקיים  .
  • טרנזיטיביות: לכל   מתקיים   ,ובאותו אופן,  .

עוד נקודות דמיון

עריכה

יש עוד נקודות דמיון, לדוגמה:

  1. סימטריה הופכית: לכל שתי פונקציות  ,‏  , ובאותו אופן,  .
  2. לכל שתי פונקציות  ,‏  , ובאותו אופן,  .

מגבלות הדמיון

עריכה

לדמיון בין הקבוצות לאופרטורים שראינו יש גם מגבלות. בין היתר:

  1. לא תמיד נכון ש , אך תמיד נכון ש .
  2. תמיד מתקיים ש , אך לא תמיד מתקיים  .


 

עכשיו תורכם:

נמק נקודות אלו.

דוגמה לשילוב מספר כללים

עריכה

נפשט את הביטוי  .


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

כעת נשתמש שוב באדיטיבות:

 
 
 
 
 


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

סיכום

עריכה

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

בהנתן אלגוריתם כלשהו, נוכל לשאול לגביו מספר שאלות, לדוגמה:

  1. מהו זמן הריצה של האלגוריתם במקרה הטוב ביותר?
  2. מהו זמן הריצה של האלגוריתם במקרה הגרוע ביותר?
  3. מהו זמן הריצה של האלגוריתם במקרה הממוצע? (לא נעסוק בכך בקורס זה, עם זאת).

לעתים נוכל לשאול שאלות מפורטות יותר אפילו:

  1. מהו זמן הריצה הטוב ביותר של חיפוש בינרי בהנחה שהאיבר נמצא במערך?
  2. מהו זמן הריצה הגרוע ביותר של חיפוש לינארי בהנחה שהאיבר אינו נמצא במערך?

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


 

כדאי לדעת:

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


הפרק הקודם:
חיפוש לינארי ובינרי
סדרי גדילה
תרגילים
הפרק הבא:
נוסחאות נסיגה