ارسال: #۱

۰۸ اردیبهشت ۱۳۹۱, ۰۶:۴۷ ب.ظ

agha_reza پرسیده:

سئوال از توابع رشد

سلام دوستان خوبید

لطفا این دو تا عکسو ببینین و منو راهنمایی کنین ، ببینم ایراد کارم کجاست ؟

فایل‌(های) پیوست شده

ارسال: #۲

۰۸ اردیبهشت ۱۳۹۱, ۰۷:۲۶ ب.ظ

Masoud05 پاسخ داده:

RE: توابع رشد

$lim \frac{n^2/logn}{n^2}=lim \frac{n^2}{n^2 * logn } = lim \frac{1}{logn}= 0$

$\frac{n^2 }{logn} \ = O (n^2)$

ارسال: #۳

۲۰ اردیبهشت ۱۳۹۱, ۰۱:۳۶ ب.ظ

fatima1537 پاسخ داده:

توابع رشد

میشه گزینه ۲ یعنی پیچیدگی n^2 .
چون در پیچیدگی ما نمیخواهیم زمان دقیق عملیات یک تابع را بدست بیاریم . و دیگه اینکه برای مقادیر بسیار زیاد n این ضرایب (مثلا در اینجا ۵)بی تاثیر هست .یا مثلا توانهایی از n که دارای درجه کمتری از n^2 هستند و با هم جمع شده اند هم تاثیر کمی دارد و قابل چشم پوشی است
مثلا برای ۲^n داریم: ۲^۲=۴ / ۲^۳=۸ / ۲^۴=۱۶ / ۲ ^۵=۳۲ /۲ ^۶=۶۴ /۲ ^۷=۱۲۸ /۲ ^۸=۲۵۶ /۲ ^۹=۵۱۲ /۲ ^۱۰=۱۰۲۴
حالا اگر مقداری مثل ۲n را با این عبارتها جمع کنیم داریم:
۲*۲=۴ / ۲*۳=۶ / ۲*۴=۸/ ۲*۵=۱۰ /۲*۶=۱۲/ ۲*۷=۱۴/ ۲*۸=۱۶/ ۲*۹=۱۸/ ۲*۱۰=۲۰
پس میبینیم که اگر ۲*۱۰=۲۰ با ۲^۱۰=۱۰۲۴ جمع بشه تاثیر چندانی روی نتیجه نهایی نداره(ودرواقع ارزش وقت گذاشتن و اهمیت دادن نداره)
همیشه برای محاسبه پیچیدگی زمانی توی چند جمله ای هایی که عبارات با هم جمع شده اند بالاترین توان را در نظر میگیریم

ارسال: #۴

۰۸ اردیبهشت ۱۳۹۱, ۰۶:۵۷ ب.ظ

fatima1537 پاسخ داده:

توابع رشد

به نظر من

$6n^{2} 20n$ از مرتبه

$n^{2}$ هست نه

$n^{3}$ و اگر اینطور باشه اونوقت عدد گذاریهای شما درست میشه
درواقع باید بگیم که

$6n^{2} 20n<=\Omega (n_{3})$ چون حداکثر این عبارتی که نوشتید و یک عبارت خطی از مرتبه ۲ هست

ارسال: #۵

۰۸ اردیبهشت ۱۳۹۱, ۰۷:۱۴ ب.ظ

Aurora پاسخ داده:

توابع رشد

در مورد سوال اول لینک های زیر کمک می کنه.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

چرا با عدد گذاری سوال رو حل کردید؟ با یک نمونه که نمیشه نقضش کرد.

ارسال: #۶

۰۸ اردیبهشت ۱۳۹۱, ۰۷:۲۲ ب.ظ

yaser_ilam_com پاسخ داده:

توابع رشد

سلام دوست من در مورد

$1/lgn$ رو نمی تونی از

$n^{2}$ جدا کنی چون در حالت جمع که نیستند چون هر دو یعنی

$n^{2} , 1/lgn$ هر دو به n وابسته و در هم ضرب شده اند میشه

$O(n^{2}/lgn)$ اما اگه به صورت

$n^{2} lgn$ بود انگاه جواب شما درسته .

همون طور دوستان گفتن با یک نمونه نمیشه حالا بیا با n=10 حساب کن می بینی غلظه

ارسال: #۷

۰۸ اردیبهشت ۱۳۹۱, ۱۱:۱۱ ب.ظ

fatima1537 پاسخ داده:

توابع رشد

$n^{2}/log n <= O(n^{2})$
نه منظور ما هم خدای نکرده این نبود.خواستیم زیادی توضیح بدیم Smile

ولی باز هم در تقسیم دو عبارت، ما نهایتا بزرگترین توان را به عنوان مرتبه زمانی در نظر میگیریم
درواقع چون بیگ او داریم پس به این معنی هست که باید

$n^{2}/log n$ کوچکتر مساوی n^2 باشد و بزرگتر از آن نمیشود ((

$n^{2}/log n <= O(n^{2})$ )).درواقع یعنی :"کران بالای تابع

$n^{2}/log n <= O(n^{2})$ حداکثر برابر n^2 است" ودیگر تابع ما بیشتر از آن رشد نمیکند

ارسال: #۸

۰۹ اردیبهشت ۱۳۹۱, ۰۲:۳۳ ق.ظ

agha_reza پاسخ داده:

توابع رشد

سپاس از دوستان

یه سوال دیگه که ترجیح دادم یه تاپیک واسش نزنم و همینجا بپرسم

تعداد mod برای تشحیص دادن اول بودن ۳۷ ایا برابره logn37 هستش ؟ ممنون

ارسال: #۹

۰۹ اردیبهشت ۱۳۹۱, ۰۲:۴۹ ق.ظ

yaser_ilam_com پاسخ داده:

RE: توابع رشد

(۰۹ اردیبهشت ۱۳۹۱ ۰۲:۳۳ ق.ظ)agha_reza نوشته شده توسط: سپاس از دوستان

یه سوال دیگه که ترجیح دادم یه تاپیک واسش نزنم و همینجا بپرسم

تعداد mod برای تشحیص دادن اول بودن ۳۷ ایا برابره logn37 هستش ؟ ممنون

اگر n فقط بر خودش و یک بخش پذیر باشد عدد اول است حال کد آن را می نویسیم .

نقل قول:

کد:

j=2; for (i=2;i<=n/2;i++) if (n mod i ==0) j++;

دقت کن نوشتیم n/2 چون بیشتر از ان حتما بر n بخش پذیر نیست و از ۲ شروع کردیم چون عدد ۱ همواره بخش پذیر است و j=2 تعداد

اعداد بخش پذیر است که عدد ۱ و n همواره بخش پذیر است حالا اگر در پایان عملیات j همان ۲ بماند n اول است.

همانطور میبینی کد همواره n/2 بار تکرار می شود لذا داریم

$O(n)$ و ربطی به

$lgn$ ندارد

در مورد n=37 داریم n/2=18 لذا میزان تکرار mod همانا ۱۶ بار است که lg37 =5.2

ارسال: #۱۰

۰۹ اردیبهشت ۱۳۹۱, ۱۰:۳۹ ق.ظ

agha_reza پاسخ داده:

توابع رشد

با سپاس
اما در گزینه ها عدد ۱۶ نیست !
سوال اینه دقیقا : فرض کنیم N=37 ، چه تعداد عملیات mod لازم است تا تعیین شود عدد N اول است ؟

۳۷ -۱۷-۱۸-log37

ارسال: #۱۱

۰۹ اردیبهشت ۱۳۹۱, ۱۰:۵۳ ق.ظ

yaser_ilam_com پاسخ داده:

RE: توابع رشد

(۰۹ اردیبهشت ۱۳۹۱ ۱۰:۳۹ ق.ظ)agha_reza نوشته شده توسط: با سپاس
اما در گزینه ها عدد ۱۶ نیست !
سوال اینه دقیقا : فرض کنیم N=37 ، چه تعداد عملیات mod لازم است تا تعیین شود عدد N اول است ؟

۳۷ -۱۷-۱۸-log37

دوست من اشتباه شد شما هم یکبار بشماری میشه ۱۷ بار Smile

(از ۲ تا ۱۸)

ارسال: #۱۲

۱۳ اردیبهشت ۱۳۹۱, ۰۴:۳۵ ب.ظ

agha_reza پاسخ داده:

توابع رشد

(n+8)(2n^2 + 2n-4) =O(n^2logn)

این رابطه غلطه چون از سمت چپ تساوی مرتبه ۲n^2 انتخاب میشه که قطعها از n^2 بیشتره ؟

ارسال: #۱۳

۱۳ اردیبهشت ۱۳۹۱, ۰۷:۳۶ ب.ظ

yaser_ilam_com پاسخ داده:

RE: توابع رشد

(۱۳ اردیبهشت ۱۳۹۱ ۰۴:۳۵ ب.ظ)agha_reza نوشته شده توسط: (n+8)(2n^2 + 2n-4) =O(n^2logn)

این رابطه غلطه چون از سمت چپ تساوی مرتبه ۲n^2 انتخاب میشه که قطعها از n^2 بیشتره ؟

ببین دوست من سمت چپ رو اول باید ضرب کنی بعد اگه ضرب بشه داریم :

$2n^{3} 18n^{2} 12n-32$

حالا میشه

$O(n^{3})$ واسه این غلطه که

$n^{3}>n^{2}lgn$

ارسال: #۱۴

۱۸ اردیبهشت ۱۳۹۱, ۱۰:۲۵ ق.ظ

agha_reza پاسخ داده:

توابع رشد

با تتشکر

پیرو پست ۹

n^2 /logn =teta(n^2)i
چرا این غلطه ؟؟؟

ارسال: #۱۵

۱۸ اردیبهشت ۱۳۹۱, ۱۰:۴۰ ق.ظ

*Najmeh* پاسخ داده:

RE: توابع رشد

(۱۸ اردیبهشت ۱۳۹۱ ۱۰:۲۵ ق.ظ)agha_reza نوشته شده توسط: با تتشکر

پیرو پست ۹

n^2 /logn =teta(n^2)i
چرا این غلطه ؟؟؟

به این دلیل که تتا باید مساوی باشن
درصورتی که
n^2 /logn<n^2

پس تتا برقرار نیست تو اون پستم گفته شده

$n^{2}\div \log n\leq O(n^{2})$

ارسال: #۱۶

۱۸ اردیبهشت ۱۳۹۱, ۱۰:۴۵ ق.ظ

yaser_ilam_com پاسخ داده:

توابع رشد

صحبت najmedj کاملا درسته ببین دوست من بهتره بری و معنی دقیق علامت های تتا و O بزرگ و کوچک و امگا کوچک و بزرگ رو کامل یاد بگیری اونوقت حل این سوالات برات ساده میشه
در تایید صحبت های قبلی ببین معنی تتا یعنی مقدار دقیق .

$\theta (n^{2})$ یعنی دقیق

$n^{2}$ نه بیشتر از این مقدار و نه کمتر .

ارسال: #۱۷

۱۹ اردیبهشت ۱۳۹۱, ۱۱:۵۱ ب.ظ

agha_reza پاسخ داده:

توابع رشد

پیچیدگی زمانی چند جمله ای کدام است ؟

p(n)= 5n^2 +100n+200000

۵n^2
n^2
۱۰۰n
۲۰۰۰۰۰

من میگم گزینه یک

ارسال: #۱۸

۲۰ اردیبهشت ۱۳۹۱, ۱۲:۰۲ ق.ظ

yaser_ilam_com پاسخ داده:

RE: توابع رشد

(۱۹ اردیبهشت ۱۳۹۱ ۱۱:۵۱ ب.ظ)agha_reza نوشته شده توسط: پیچیدگی زمانی چند جمله ای کدام است ؟

p(n)= 5n^2 +100n+200000

ضرایب پشت متغیرها اگه ثابت باشند کنار بزارید پیچیدگی میشه

$\theta (n^{2} )$

دلیل :
زمانی که n بزرگ بشه یعنی

$n\rightarrow \infty$ بیشترین رو بدون در نظر گرفتن ضرایب ثابت و متغیر های کمتر صحیح است .

متوجه نشدی بازم توضیح بدم

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	جایی برای پیدا کردن توابع آماده جاوااسکریپت	f.b	۷	۵,۰۰۸	۲۰ آذر ۱۳۹۹ ۰۴:۰۸ ب.ظ آخرین ارسال: calm
	تعداد توابع پوشا	ss311	۰	۲,۲۴۷	۰۶ بهمن ۱۳۹۸ ۰۴:۵۷ ب.ظ آخرین ارسال: ss311
	مشکل با درک توابع دنباله دار و مولد ؟؟؟؟	radar	۰	۲,۸۹۷	۱۶ دى ۱۳۹۷ ۰۴:۳۶ ب.ظ آخرین ارسال: radar
	دو سئوال طراحی الگوریتم	java50	۱	۱,۸۵۵	۱۱ اسفند ۱۳۹۵ ۰۱:۱۲ ق.ظ آخرین ارسال: alireza01
	معنی بهینگی کمتر در توابع هیورستیک	MBe	۱	۲,۲۰۲	۰۸ دى ۱۳۹۵ ۰۲:۰۱ ب.ظ آخرین ارسال: Saman
	رشد تابع سینوسی	shamim1395	۴	۲,۱۸۶	۳۰ آذر ۱۳۹۵ ۰۳:۳۸ ب.ظ آخرین ارسال: shamim1395
	محاسبه رشد تابع	H-Arshad	۴	۴,۳۰۰	۱۱ آذر ۱۳۹۵ ۰۴:۳۱ ق.ظ آخرین ارسال: Iranian Wizard
	محاسبه رشد تابع موازی	H-Arshad	۱	۱,۸۷۷	۱۰ آذر ۱۳۹۵ ۰۸:۲۱ ق.ظ آخرین ارسال: Jooybari
	نحوه محاسبه درجه رشد	Majiid	۱	۲,۵۱۶	۲۷ آبان ۱۳۹۵ ۰۵:۴۵ ب.ظ آخرین ارسال: Behnam‌
	مقایسه توابع و استفاده از حد	maneshti	۳	۲,۶۰۱	۲۴ آبان ۱۳۹۵ ۰۴:۵۷ ب.ظ آخرین ارسال: maneshti

سئوال از توابع رشد

سئوال از توابع رشد

RE: توابع رشد

توابع رشد

توابع رشد

توابع رشد

توابع رشد

توابع رشد

توابع رشد

RE: توابع رشد

توابع رشد

RE: توابع رشد

توابع رشد

RE: توابع رشد

توابع رشد

RE: توابع رشد

توابع رشد

توابع رشد

RE: توابع رشد

Can I see some ID?

Feeling left out?

رمزت رو فراموش کردی؟

Feeling left out?