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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש

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

דוגמה

אם אנו חושדים שזמן הריצה t כתלות ב־n פרופורציוני ל־n^r:

t\propto n^r
\Downarrow
t=cn^r
\ln t=\ln c+r\ln n

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

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

f\left ( n \right )=\Theta\left ( g\left ( n \right ) \right ) אם \forall n, A\cdot g\left ( n \right )\leq f\left ( n \right )\leq B\cdot g\left ( n \right ).

f\left ( n \right )=O \left ( g\left ( n \right ) \right ) אם \forall n, f\left ( n \right )\leq B\cdot g\left ( n \right ).


דוגמה:

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


דוגמה נוספת:

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


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


דוגמה:

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


דוגמה נוספת:

\ln x=o\left ( x \right ) וגם \ln x=O\left ( x \right ).