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

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

$Onotation$

תהי $g(n)$ פונקציה שואפת לאינסוף.

נסמן $f=O(g)$ אם ורק אם קיימים $c>0$-ים לכל $m\in \mathbb{N}$ כך שעבור כל $n\ge m$ מתקיים ש- $f(n)\le c*g(n)$

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

• 
  תיאור התמונה
• 
  קיים $1=c>0$ ו-$x_0=m=5$ עבורם $f(x)\le cg(x)$ כל זמן ש- <math>

דוגמות

1. תהי $g(n)=n$ ו-$f(n)=2n+2$ אז נוכל לומר כי $f=O(n)$ (הצבה $g(x)$) מפני שעבור כל $c=3,m=2$ בהכרח מתקיים ש-$2n+2\le 3*n$ (*)
2. תהי $g(x)=x^4$ ו-$f(x)=6x^4-2x^3$ אז נוכל לומר כי $f=O(x^4)$ (הצבה $g(x)$) מפני שעבור כל $c=13,m=1$ בהכרח מתקיים ש-$6x^4-2x^3\le x^4$
3. תהי $g(n)=n$ אזי עבור $log(n),n,nlog(n),n^2,n^3...$ נוכל לומר כי $f=O(g)$

Big Theta

1. תהי $f=\mathrm{\Omega }(g)$ אם ורק אם $g=O(f)$ כלומר אם מתקיים ש-$g$ מתפקדת כ-$O$ אז נסמן אותה $f=\mathrm{\Omega }(g)$.

דוגמות

תהי $g(n)=n$ ו-$f(n)=2n+2$ אז נוכל לומר כי $g=O(2n+2)$ (הצבה $f(x)$) מפני שעבור כל $c=1,m=1$ בהכרח מתקיים ש-$n\le 1*(2n+2)$ ולכן $\mathrm{\Omega }(n)=2n+1$ (**)

Big Omega

$f=\mathrm{\Theta }(g)$ אם ורק אם $f=O(g)$ וגם $f=\mathrm{\Omega }(g)$ כלומר ל-$f$ יש $O(g)$, ולאותו הפונקציה, $g$ מתקיים שיש $O$ שהוא הפונקציה $f$ עצמה, $g=O(f)$ .

דוגמות

1. הוכחנו כי אם מתקיים ש-$g(n)=n$ ו-$f(n)=2n+2$ אז$f=O(n)$ (*) וגם מתקיים ש- $g=O(f)$ (**) ולכן $\mathrm{\Theta }(g)=2n+1$.
2. $\mathrm{\forall }a>1lo{g}_{a}n=\mathrm{\Theta }(lo{g}_{2}n)$ (נובע מזהות $lo{g}_{a}n=\frac{lo{g}_{2}n}{lo{g}_{2}a}$

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

• 
  תיאור התמונה
• 
  תיאור התמונה