פייתון/פייתון גרסה 3/סיבוכיות/סימון אסימפטוטי

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

עריכה

תהי   פונקציה שואפת לאינסוף.

נסמן   אם ורק אם קיימים  -ים לכל   כך שעבור כל   מתקיים ש-  

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

דוגמותעריכה

  1. תהי   ו-  אז נוכל לומר כי   (הצבה  ) מפני שעבור כל   בהכרח מתקיים ש-  (*)
  2. תהי   ו-  אז נוכל לומר כי   (הצבה  ) מפני שעבור כל   בהכרח מתקיים ש- 
  3. תהי   אזי עבור   נוכל לומר כי  

Big Thetaעריכה

  1. תהי   אם ורק אם   כלומר אם מתקיים ש-  מתפקדת כ-  אז נסמן אותה  .

דוגמותעריכה

תהי   ו-  אז נוכל לומר כי   (הצבה  ) מפני שעבור כל   בהכרח מתקיים ש-  ולכן   (**)

Big Omegaעריכה

  אם ורק אם   וגם   כלומר ל-  יש  , ולאותו הפונקציה,   מתקיים שיש   שהוא הפונקציה   עצמה,   .

דוגמותעריכה

  1. הוכחנו כי אם מתקיים ש-  ו-  אז  (*) וגם מתקיים ש-   (**) ולכן  .
  2.   (נובע מזהות  

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