תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, יעילות

חזרה לקישורים לתקצירים

דוגמה

אם אנו חושדים שזמן הריצה [math]\displaystyle{ t }[/math] כתלות ב־[math]\displaystyle{ n }[/math] פרופורציוני ל־[math]\displaystyle{ n^r }[/math]:

[math]\displaystyle{ t\propto n^r }[/math]
[math]\displaystyle{ \Downarrow }[/math]
[math]\displaystyle{ t=cn^r }[/math]
[math]\displaystyle{ \ln t=\ln c+r\ln n }[/math]

לכן [math]\displaystyle{ \ln t }[/math] כתלות ב־[math]\displaystyle{ \ln n }[/math] הינו קו ישר ששיפועו [math]\displaystyle{ r }[/math], וכך ניתן למצוא את [math]\displaystyle{ \ln c }[/math] כחיתוך עם ציר y.

מספר הגדרות ודוגמות

[math]\displaystyle{ f\left ( n \right )=\Theta\left ( g\left ( n \right ) \right ) }[/math] אם [math]\displaystyle{ \forall n, A\cdot g\left ( n \right )\leq f\left ( n \right )\leq B\cdot g\left ( n \right ) }[/math].

[math]\displaystyle{ f\left ( n \right )=O \left ( g\left ( n \right ) \right ) }[/math] אם [math]\displaystyle{ \forall n, f\left ( n \right )\leq B\cdot g\left ( n \right ) }[/math].

דוגמה:

[math]\displaystyle{ e^x=1+x+\frac{x^2}{2}+...=\sum_{n=0}^\infty\frac{x^n}{n!} }[/math], לכן [math]\displaystyle{ e^x=1+x+\frac{x^2}{2}+O(x^3) }[/math].
באופן מדויק: [math]\displaystyle{ e^x=1+x+\frac{x^2}{2}+\frac{(x^*)^3}{6} }[/math] כאשר [math]\displaystyle{ |x^*|\lt |x| }[/math], ולכן [math]\displaystyle{ \frac{(x^*)^3}{6}\leq\frac{1}{6} x^3 }[/math].

דוגמה נוספת:

בחיפוש בינארי מבוצעות [math]\displaystyle{ \left \lceil \log_2 n\right \rceil }[/math] פעולות, ולכן היעילות הינה [math]\displaystyle{ \left \lceil \log_2 n\right \rceil=O(\log_2 n)=O(\ln n) }[/math].

[math]\displaystyle{ f\left ( n \right )=o\left ( g\left ( n \right ) \right ) }[/math] אם [math]\displaystyle{ \lim_{n\rightarrow\infty}\frac{f\left ( n \right )}{g\left ( n \right )}=0 }[/math].

דוגמה:

[math]\displaystyle{ e^{-x}=o\left ( x^n \right ) }[/math] כי [math]\displaystyle{ \lim_{x\rightarrow\infty}\frac{e^{-x}}{x^n}=0 }[/math]

דוגמה נוספת:

[math]\displaystyle{ \ln x=o\left ( x \right ) }[/math] וגם [math]\displaystyle{ \ln x=O\left ( x \right ) }[/math].