לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

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

[עריכה]

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

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

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

דוגמות

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

Big Theta

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

דוגמות

[עריכה]

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

Big Omega

[עריכה]

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

דוגמות

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

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

[עריכה]