שינויים

סיבוכיות

נוספו 344 בתים, 11:53, 24 בנובמבר 2011
/* יחסים בין פונקציות נפוצות */
* היחס <math>f(n)=\Theta(g(n))</math> הוא יחס שקילות.
* <math>f(n)+o(f(n))=\Theta(f(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>1\leq a<b</math> ממשיים <math>a^n\ll b^n</math>.
485
עריכות