הבדלים בין גרסאות בדף "סיבוכיות"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏תכונות בסיסיות)
(←‏תכונות בסיסיות)
שורה 22: שורה 22:
 
נניח כי <math>f,g:\mathbb{N}\to\mathbb{R}_{\geq 0}</math> אזי:
 
נניח כי <math>f,g:\mathbb{N}\to\mathbb{R}_{\geq 0}</math> אזי:
 
*<math>f(n)=O(f(n))</math>. כנ"ל עבור <math>\Theta,\Omega</math>. (זהירות: <math>f(n)\neq o(f(n))</math>!)
 
*<math>f(n)=O(f(n))</math>. כנ"ל עבור <math>\Theta,\Omega</math>. (זהירות: <math>f(n)\neq o(f(n))</math>!)
 +
*<math>f(n)=O(g(n)</math> אם ורק אם <math>g(n)=\Omega(f(n))</math>.

גרסה מ־14:30, 3 בנובמבר 2011

סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-0).


או גדול, אומגה, תטה

הגדרה תהיינה f,g:\mathbb{N}\to\mathbb{R}_{\geq 0} פונקציות אי שליליות מהטבעיים לממשיים.

  • נאמר ש-f(n)=O(g(n)) אם קיים C>0 ממשי ו-n_0\in\mathbb{N} כך ש-f(n)\leq Cg(n) לכל n>n_0 (הקבוע C יכול להיות גדול כרצוננו).
  • נאמר ש-f(n)=\Omega(g(n)) אם קיים C>0 ממשי ו-n_0\in\mathbb{N} כך ש-f(n)\geq Cg(n) לכל n>n_0 (הקבוע C יכול קטן גדול כרצוננו).
  • נאמר ש-f(n)=\Theta(g(n)) אם f(n)=O(g(n)) וגם f(n)=\Omega(g(n)), כלומר קיימים C_1,C_2>0 ממשיים ו-n_0\in\mathbb{N} כך ש-C_1g(n)\leq f(n)\leq C_2g(n) לכל n>n_0.

לעיתים משתמשים גם בהגדה הבאה:

  • נאמר ש-f(n)=o(g(n)) (סימון אחר f(n)\ll g(n)) אם \lim_{n\to\infty}\left|\frac{f(n)}{g(n)}\right|=0. (הגדרה זו תקפה גם עבור פונקציות המקבלות ערכים שליליים ולכן הערך המוחלט.)

דוגמא: אם f(n)=n^3 ו-g(n)=2n^2 אז לא קשה לראות ש-f(n)=\Omega(g(n)) ו-g(n)=O(f(n)) אבל לא מתקיים f(n)=\Theta(g(n)).

קצת אינטואיציה: f(n)=O(g(n)) אומר ש-f גדלה כמו g או פחות מכך (עד כדי כפל בקבוע). f(n)=\Omega(g(n)) אומר ש-f גדלה כמו g או יותר מכך (עד כדי כפל בקבוע).

הערה: כשכותבים O(f(n)) בחישובים (לדוגמא: n+O(\lg n)) בדרך כלל מתכוונים לפונקציה שהיא O(f(n)). הנ"ל נכון גם עבור \Theta,\Omega,o.

הערה: ההגדרות לעיל תקפות גם עבור פונקציות מ-\mathbb{R}_{\geq 0} ל-\mathbb{R}_{\geq 0}

תכונות בסיסיות

נניח כי f,g:\mathbb{N}\to\mathbb{R}_{\geq 0} אזי:

  • f(n)=O(f(n)). כנ"ל עבור \Theta,\Omega. (זהירות: f(n)\neq o(f(n))!)
  • f(n)=O(g(n) אם ורק אם g(n)=\Omega(f(n)).
מקור: https://math-wiki.com/index.php?title=סיבוכיות&oldid=15652