הבדלים בין גרסאות בדף "סיבוכיות"
מתוך Math-Wiki
(←או גדול, אומגה, תטה) |
(←או גדול, אומגה, תטה) |
||
שורה 11: | שורה 11: | ||
'''דוגמא:''' אם <math>f(n)=n^3</math> ו-<math>g(n)=2n^2</math> אז לא קשה לראות ש-<math>f(n)=\Omega(g(n))</math> ו-<math>g(n)=O(f(n))</math> אבל לא מתקיים <math>f(n)=\Theta(g(n))</math>. | '''דוגמא:''' אם <math>f(n)=n^3</math> ו-<math>g(n)=2n^2</math> אז לא קשה לראות ש-<math>f(n)=\Omega(g(n))</math> ו-<math>g(n)=O(f(n))</math> אבל לא מתקיים <math>f(n)=\Theta(g(n))</math>. | ||
+ | |||
+ | '''קצת אינטואיציה:''' <math>f(n)=O(g(n))</math> אומר ש-<math>f</math> גדלה כמו <math>g</math> או פחות מכך (עד כדי כפל בקבוע). <math>f(n)=\Omega(g(n))</math> אומר ש-<math>f</math> גדלה כמו <math>g</math> או יותר מכך (עד כדי כפל בקבוע). | ||
'''הערה:''' כשכותבים <math>O(f(n))</math> בחישובים (לדוגמא: <math>n+O(\lg n)</math>) בדרך כלל מתכוונים לפונקציה שהיא <math>O(f(n))</math>. הנ"ל נכון גם עבור <math>\Theta,\Omega,o</math>. | '''הערה:''' כשכותבים <math>O(f(n))</math> בחישובים (לדוגמא: <math>n+O(\lg n)</math>) בדרך כלל מתכוונים לפונקציה שהיא <math>O(f(n))</math>. הנ"ל נכון גם עבור <math>\Theta,\Omega,o</math>. | ||
'''הערה:''' ההגדרות לעיל תקפות גם עבור פונקציות מ-<math>\mathbb{R}_{\geq 0}</math> ל-<math>\mathbb{R}_{\geq 0}</math> | '''הערה:''' ההגדרות לעיל תקפות גם עבור פונקציות מ-<math>\mathbb{R}_{\geq 0}</math> ל-<math>\mathbb{R}_{\geq 0}</math> | ||
− | |||
== תכונות בסיסיות == | == תכונות בסיסיות == |
גרסה מ־14:26, 3 בנובמבר 2011
סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-0).
או גדול, אומגה, תטה
הגדרה תהיינה פונקציות אי שליליות מהטבעיים לממשיים.
- נאמר ש- אם קיים ממשי ו- כך ש- לכל (הקבוע יכול להיות גדול כרצוננו).
- נאמר ש- אם קיים ממשי ו- כך ש- לכל (הקבוע יכול קטן גדול כרצוננו).
- נאמר ש- אם וגם , כלומר קיימים ממשיים ו- כך ש- לכל .
לעיתים משתמשים גם בהגדה הבאה:
- נאמר ש- (סימון אחר ) אם . (הגדרה זו תקפה גם עבור פונקציות המקבלות ערכים שליליים ולכן הערך המוחלט.)
דוגמא: אם ו- אז לא קשה לראות ש- ו- אבל לא מתקיים .
קצת אינטואיציה: אומר ש- גדלה כמו או פחות מכך (עד כדי כפל בקבוע). אומר ש- גדלה כמו או יותר מכך (עד כדי כפל בקבוע).
הערה: כשכותבים בחישובים (לדוגמא: ) בדרך כלל מתכוונים לפונקציה שהיא . הנ"ל נכון גם עבור .
הערה: ההגדרות לעיל תקפות גם עבור פונקציות מ- ל-
תכונות בסיסיות
נניח כי אזי:
- . כנ"ל עבור .