صفحه‌ها: ۱ ۲
صحبت najmedj کاملا درسته ببین دوست من بهتره بری و معنی دقیق علامت های تتا و O بزرگ و کوچک و امگا کوچک و بزرگ رو کامل یاد بگیری اونوقت حل این سوالات برات ساده میشه
در تایید صحبت های قبلی ببین معنی تتا یعنی مقدار دقیق . [tex]\theta (n^{2})[/tex] یعنی دقیق [tex]n^{2}[/tex] نه بیشتر از این مقدار و نه کمتر .
پیچیدگی زمانی چند جمله ای کدام است ؟
p(n)= 5n^2 +100n+200000
۵n^2
n^2
۱۰۰n
۲۰۰۰۰۰
من میگم گزینه یک
(۱۹ اردیبهشت ۱۳۹۱ ۱۱:۵۱ ب.ظ)agha_reza نوشته شده توسط: پیچیدگی زمانی چند جمله ای کدام است ؟
p(n)= 5n^2 +100n+200000
ضرایب پشت متغیرها اگه ثابت باشند کنار بزارید پیچیدگی میشه [tex]\theta (n^{2} )[/tex]
دلیل :
زمانی که n بزرگ بشه یعنی [tex]n\rightarrow \infty[/tex] بیشترین رو بدون در نظر گرفتن ضرایب ثابت و متغیر های کمتر صحیح است .
متوجه نشدی بازم توضیح بدم
میشه گزینه ۲ یعنی پیچیدگی n^2 .
چون در پیچیدگی ما نمیخواهیم زمان دقیق عملیات یک تابع را بدست بیاریم . و دیگه اینکه برای مقادیر بسیار زیاد n این ضرایب (مثلا در اینجا ۵)بی تاثیر هست .یا مثلا توانهایی از n که دارای درجه کمتری از n^2 هستند و با هم جمع شده اند هم تاثیر کمی دارد و قابل چشم پوشی است
مثلا برای ۲^n داریم: ۲^۲=۴ / ۲^۳=۸ / ۲^۴=۱۶ / ۲ ^۵=۳۲ /۲ ^۶=۶۴ /۲ ^۷=۱۲۸ /۲ ^۸=۲۵۶ /۲ ^۹=۵۱۲ /۲ ^۱۰=۱۰۲۴
حالا اگر مقداری مثل ۲n را با این عبارتها جمع کنیم داریم:
۲*۲=۴ / ۲*۳=۶ / ۲*۴=۸/ ۲*۵=۱۰ /۲*۶=۱۲/ ۲*۷=۱۴/ ۲*۸=۱۶/ ۲*۹=۱۸/ ۲*۱۰=۲۰
پس میبینیم که اگر ۲*۱۰=۲۰ با ۲^۱۰=۱۰۲۴ جمع بشه تاثیر چندانی روی نتیجه نهایی نداره(ودرواقع ارزش وقت گذاشتن و اهمیت دادن نداره)
همیشه برای محاسبه پیچیدگی زمانی توی چند جمله ای هایی که عبارات با هم جمع شده اند بالاترین توان را در نظر میگیریم