تحلیل الگوریتم‌ها: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
خط ۶۰:
است.
طبق تعریفی که در قسمت تابع <math>\mathcal{O}</math> خواهیم گفت، با وجود داشتن <math>c = (c_1+c_2+c_3+c_4)</math> و درست بودن رابطه <math>0<f(n)<c.n^2</math> برای هر <math>n >1</math> خواهیم دید که الگوریتم بالا <math>\mathcal{O}(n^2)</math> است.
خط ۱۳۷:
2.برای تابع<math>g(n)</math> تابع <math>\mathcal{O}(g(n))</math> را به صورت مجموعه توابع زیر تعریف میکنیم:
:<math>\mathcal{O}(g(n))
ُیعنی آهنگ رشد تابع <math>g(n)</math> برای مقادیر بزرگ n، بیشتر یا مساوی آهنگ رشد تابع <math>f(n)</math> است. در این صورت می‌گوییم تابع <math>g(n)</math> '''کران بالای مجانبی''' برای <math>f(n)</math> است و معمولا به کار میبریم:
خط ۱۴۳:
3.برای تابع<math>g(n)</math> تابع <math>\varOmega(g(n))</math> را به صورت مجموعه توابع زیر تعریف میکنیم:
:<math>\varOmega(g(n)) = \{f(n): \exists c > 0\ and\ n_0,\ such\ that \ \forall n\ge n_0 0\le
ُیعنی آهنگ رشد تابع <math>g(n)</math> برای مقادیر بزرگ n، کند تر یا مساوی آهنگ رشد تابع <math>f(n)</math> است. در این صورت می‌گوییم تابع <math>g(n)</math> '''کران پایین مجانبی''' برای <math>f(n)</math> است و معمولا به کار میبریم:
| |||