סיבוכיות - היסטוריית גרסאות

Ufirst: /* יחסים בין פונקציות נפוצות */

2011-11-24T11:53:08Z

יחסים בין פונקציות נפוצות

→ הגרסה הקודמת		גרסה מ־11:53, 24 בנובמבר 2011
שורה 33:		שורה 33:
	== יחסים בין פונקציות נפוצות ==		== יחסים בין פונקציות נפוצות ==

	* לכל <math>a,b,c,d>0</math> ממשיים מתקיים <math>\dots\ll (\ln\ln n)^a\ll (\ln n)^b\ll n^c\ll d^n\ll n!\ll n^n</math>.		* לכל <math>a,b,c>0</math> ו-<math>d>1</math> ממשיים מתקיים <math>\dots\ll (\ln\ln n)^a\ll (\ln n)^b\ll n^c\ll d^n\ll n!\ll n^n</math>.
	* לכל <math>a<b</math> ממשיים <math>n^a\ll n^b</math>.		* לכל <math>a<b</math> ממשיים <math>n^a\ll n^b</math>.
	* לכל <math>1\leq a<b</math> ממשיים <math>a^n\ll b^n</math>.		* לכל <math>1\leq a<b</math> ממשיים <math>a^n\ll b^n</math>.

Ufirst: /* יחסים בין פונקציות נפוצות */

2011-11-24T11:52:28Z

יחסים בין פונקציות נפוצות

→ הגרסה הקודמת		גרסה מ־11:52, 24 בנובמבר 2011
שורה 32:		שורה 32:

	== יחסים בין פונקציות נפוצות ==		== יחסים בין פונקציות נפוצות ==

			* לכל <math>a,b,c,d>0</math> ממשיים מתקיים <math>\dots\ll (\ln\ln n)^a\ll (\ln n)^b\ll n^c\ll d^n\ll n!\ll n^n</math>.
			* לכל <math>a<b</math> ממשיים <math>n^a\ll n^b</math>.
			* לכל <math>1\leq a<b</math> ממשיים <math>a^n\ll b^n</math>.

Ufirst ב־11:48, 24 בנובמבר 2011

2011-11-24T11:48:33Z

→ הגרסה הקודמת		גרסה מ־11:48, 24 בנובמבר 2011
שורה 29:		שורה 29:
	* היחס <math>f(n)=\Theta(g(n))</math> הוא יחס שקילות.		* היחס <math>f(n)=\Theta(g(n))</math> הוא יחס שקילות.
	* <math>f(n)+o(f(n))=\Theta(f(n))</math>.		* <math>f(n)+o(f(n))=\Theta(f(n))</math>.


			== יחסים בין פונקציות נפוצות ==

Ufirst: /* תכונות בסיסיות */

2011-11-24T11:47:35Z

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

→ הגרסה הקודמת		גרסה מ־11:47, 24 בנובמבר 2011
שורה 26:		שורה 26:
	* <math>O(f(n))\cdot O(g(n))=O(f(n)g(n))</math>. כנ"ל עבור <math>\Theta, \Omega</math>.		* <math>O(f(n))\cdot O(g(n))=O(f(n)g(n))</math>. כנ"ל עבור <math>\Theta, \Omega</math>.
	* <math>O(f(n))^\alpha=O(f(n)^\alpha)</math> לכל <math>\alpha>0</math>. כנ"ל עבור <math>\Theta,\Omega</math>.		* <math>O(f(n))^\alpha=O(f(n)^\alpha)</math> לכל <math>\alpha>0</math>. כנ"ל עבור <math>\Theta,\Omega</math>.
	* היחס <math>f(n)=O(g(n))</math> הוא טרנזיטיבי. (ניסוח אחר: <math>O(O(f(n)))=O(f(n))</math>.) כנ"ל עבור <math>\Omega</math>.		* היחס <math>f(n)=O(g(n))</math> הוא טרנזיטיבי. (ניסוח אחר: <math>O(O(f(n)))=O(f(n))</math>.) כנ"ל עבור <math>\Theta,\Omega</math>.
	* היחס <math>f(n)=\Theta(g(n))</math> הוא יחס שקילות. ~~(ניסוח אחר: <math>\Theta(\Theta(f(n)))=\Theta(f(n))</math>.)~~		* היחס <math>f(n)=\Theta(g(n))</math> הוא יחס שקילות.
	* <math>f(n)+o(f(n))=\Theta(f(n))</math>.		* <math>f(n)+o(f(n))=\Theta(f(n))</math>.

Ufirst: /* תכונות בסיסיות */

2011-11-24T11:46:48Z

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

→ הגרסה הקודמת		גרסה מ־11:46, 24 בנובמבר 2011
שורה 26:		שורה 26:
	* <math>O(f(n))\cdot O(g(n))=O(f(n)g(n))</math>. כנ"ל עבור <math>\Theta, \Omega</math>.		* <math>O(f(n))\cdot O(g(n))=O(f(n)g(n))</math>. כנ"ל עבור <math>\Theta, \Omega</math>.
	* <math>O(f(n))^\alpha=O(f(n)^\alpha)</math> לכל <math>\alpha>0</math>. כנ"ל עבור <math>\Theta,\Omega</math>.		* <math>O(f(n))^\alpha=O(f(n)^\alpha)</math> לכל <math>\alpha>0</math>. כנ"ל עבור <math>\Theta,\Omega</math>.
			* היחס <math>f(n)=O(g(n))</math> הוא טרנזיטיבי. (ניסוח אחר: <math>O(O(f(n)))=O(f(n))</math>.) כנ"ל עבור <math>\Omega</math>.
			* היחס <math>f(n)=\Theta(g(n))</math> הוא יחס שקילות. (ניסוח אחר: <math>\Theta(\Theta(f(n)))=\Theta(f(n))</math>.)
			* <math>f(n)+o(f(n))=\Theta(f(n))</math>.

Ufirst: /* תכונות בסיסיות */

2011-11-24T11:40:30Z

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

→ הגרסה הקודמת		גרסה מ־11:40, 24 בנובמבר 2011
שורה 23:		שורה 23:
	*<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>.		*<math>f(n)=O(g(n))</math> אם ורק אם <math>g(n)=\Omega(f(n))</math>.
			* <math>O(f(n))+O(g(n))=O(f(n)+g(n))</math>. כנ"ל עבור <math>\Theta,\Omega</math>.
			* <math>O(f(n))\cdot O(g(n))=O(f(n)g(n))</math>. כנ"ל עבור <math>\Theta, \Omega</math>.
			* <math>O(f(n))^\alpha=O(f(n)^\alpha)</math> לכל <math>\alpha>0</math>. כנ"ל עבור <math>\Theta,\Omega</math>.

Ufirst: /* תכונות בסיסיות */

2011-11-03T14:31:26Z

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

→ הגרסה הקודמת		גרסה מ־14:31, 3 בנובמבר 2011
שורה 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>.		*<math>f(n)=O(g(n))</math> אם ורק אם <math>g(n)=\Omega(f(n))</math>.

Ufirst: /* תכונות בסיסיות */

2011-11-03T14:30:20Z

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

→ הגרסה הקודמת		גרסה מ־14:30, 3 בנובמבר 2011
שורה 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>.

Ufirst: /* תכונות בסיסיות */

2011-11-03T14:27:26Z

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

→ הגרסה הקודמת		גרסה מ־14:27, 3 בנובמבר 2011
שורה 21:		שורה 21:

	נניח כי <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)=O(f(n))</math>. כנ"ל עבור <math>\Theta,\Omega</math>. (זהירות: <math>f(n)\neq o(f(n))</math>!)

Ufirst: /* או גדול, אומגה, תטה */

2011-11-03T14:26:30Z

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

→ הגרסה הקודמת		גרסה מ־14:26, 3 בנובמבר 2011
שורה 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>


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