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

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

$O\ notation$

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

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

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

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

דוגמות

1. תהי $g(n)=n$ ו-$f(n)=2n+2$ אז נוכל לומר כי $f=O(n)$ (הצבה $g(x)$) מפני שעבור כל $c=3,\ m=2$ בהכרח מתקיים ש-$2n+2\leq 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}\leq x^{4}$
3. תהי $g(n)=n$ אזי עבור $log(n),n,nlog(n),n^{2},n^{3}...$ נוכל לומר כי $f=O(g)$

Big Theta

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

דוגמות

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

Big Omega

$\ f=\Theta (g)$ אם ורק אם $\ f=O(g)$ וגם $\ f=\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)$ (**) ולכן $\Theta (g)=2n+1$.
2. $\forall a>1\ log_{a}n=\Theta (log_{2}n)$ (נובע מזהות $log_{a}n={\frac {log_{2}n}{log_{2}a}}$

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

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