|
# '''[[/סיבוכיות זמן/]]''' - זמן ריצה, כמות הזמן הנדרשת לתכנית לרוץ במקרה הרע ביותר.
# '''[[/סיבוכיות מקום/]]''' - מקום בזיכרון שתוספת התכנית.
=סיבוכיות זמן=
==<math>O \ notation</math>==
[[File:Big-O-notation.png|300px|thumb|דוגמה נוספת. קיים <math>1=c>0</math> ו-<math>x_0=m=5</math> עבורם <math>f(x) \le cg(x)</math> כל זמן ש- <math>
x \ge x_0
</math>]]
תהי <math>\ g(n)</math> פונקציה שואפת לאינסוף.
נסמן <math>f= O(g)</math> אם ורק אם קיימים <math>c>0</math>-ים לכל <math>m\in\mathbb{N}</math> כך שעבור כל <math>n\ge m</math> מתקיים ש- <math>f(n) \le c*g(n)</math>
כלומר עבור ערכי <math>n</math> הולכים וגדלים שמקבלת <math>\ f</math>, היא קטנה יותר מ-<math>\ g</math> עד כדי כפל בקבוע.
דוגמות:
# תהי <math>g(n) = n</math> ו-<math>f(n) = 2n +2</math> אז נוכל לומר כי <math>f= O(n)</math> (הצבה <math>g(x)</math>) מפני שעבור כל <math>c=3,\ m=2</math> בהכרח מתקיים ש-<math>2n+2 \le 3*n</math>
# תהי <math>g(x)=x^4</math> ו-<math>f(x)=6x^4 -2x^3</math> אז נוכל לומר כי <math>f= O(x^4)</math> (הצבה <math>g(x)</math>) מפני שעבור כל <math>c=13,\ m=1</math> בהכרח מתקיים ש-<math>6x^4 -2x^3 \le x^4</math>
# תהי <math>g(n) = n</math> אזי עבור <math>log(n), n, nlog(n), n^2, n^3...</math> נוכל לומר כי <math>f= O(g)</math>
===פעולות עם זמן ריצה <math>O(n)</math>===
# פעולות אריתמטיות <math>(+, -, *, /,%)</math>
# פעולות השוואה <math>(<,>, ==,! =)</math>
# [[פייתון/פייתון גרסה 3/משתנים|הצהרה משתנה]]
# [[פייתון/פייתון גרסה 3/משתנים|פקודת השמה]]
# שימוש במתודה או בפונקציה (ראה טבלה)
=סיבוכיות מקום=
=ראה גם=
| 