۰
subtitle
ارسال: #۱
سئوال از توابع رشد
سلام دوستان خوبید
لطفا این دو تا عکسو ببینین و منو راهنمایی کنین ، ببینم ایراد کارم کجاست ؟
لطفا این دو تا عکسو ببینین و منو راهنمایی کنین ، ببینم ایراد کارم کجاست ؟
۰
ارسال: #۲
RE: توابع رشد
[tex]lim \frac{n^2/logn}{n^2}=lim \frac{n^2}{n^2 * logn } = lim \frac{1}{logn}= 0[/tex]
[tex]\frac{n^2 }{logn} \ = O (n^2) [/tex]
[tex]\frac{n^2 }{logn} \ = O (n^2) [/tex]
۰
ارسال: #۳
توابع رشد
میشه گزینه ۲ یعنی پیچیدگی n^2 .
چون در پیچیدگی ما نمیخواهیم زمان دقیق عملیات یک تابع را بدست بیاریم . و دیگه اینکه برای مقادیر بسیار زیاد n این ضرایب (مثلا در اینجا ۵)بی تاثیر هست .یا مثلا توانهایی از n که دارای درجه کمتری از n^2 هستند و با هم جمع شده اند هم تاثیر کمی دارد و قابل چشم پوشی است
مثلا برای ۲^n داریم: ۲^۲=۴ / ۲^۳=۸ / ۲^۴=۱۶ / ۲ ^۵=۳۲ /۲ ^۶=۶۴ /۲ ^۷=۱۲۸ /۲ ^۸=۲۵۶ /۲ ^۹=۵۱۲ /۲ ^۱۰=۱۰۲۴
حالا اگر مقداری مثل ۲n را با این عبارتها جمع کنیم داریم:
۲*۲=۴ / ۲*۳=۶ / ۲*۴=۸/ ۲*۵=۱۰ /۲*۶=۱۲/ ۲*۷=۱۴/ ۲*۸=۱۶/ ۲*۹=۱۸/ ۲*۱۰=۲۰
پس میبینیم که اگر ۲*۱۰=۲۰ با ۲^۱۰=۱۰۲۴ جمع بشه تاثیر چندانی روی نتیجه نهایی نداره(ودرواقع ارزش وقت گذاشتن و اهمیت دادن نداره)
همیشه برای محاسبه پیچیدگی زمانی توی چند جمله ای هایی که عبارات با هم جمع شده اند بالاترین توان را در نظر میگیریم
چون در پیچیدگی ما نمیخواهیم زمان دقیق عملیات یک تابع را بدست بیاریم . و دیگه اینکه برای مقادیر بسیار زیاد n این ضرایب (مثلا در اینجا ۵)بی تاثیر هست .یا مثلا توانهایی از n که دارای درجه کمتری از n^2 هستند و با هم جمع شده اند هم تاثیر کمی دارد و قابل چشم پوشی است
مثلا برای ۲^n داریم: ۲^۲=۴ / ۲^۳=۸ / ۲^۴=۱۶ / ۲ ^۵=۳۲ /۲ ^۶=۶۴ /۲ ^۷=۱۲۸ /۲ ^۸=۲۵۶ /۲ ^۹=۵۱۲ /۲ ^۱۰=۱۰۲۴
حالا اگر مقداری مثل ۲n را با این عبارتها جمع کنیم داریم:
۲*۲=۴ / ۲*۳=۶ / ۲*۴=۸/ ۲*۵=۱۰ /۲*۶=۱۲/ ۲*۷=۱۴/ ۲*۸=۱۶/ ۲*۹=۱۸/ ۲*۱۰=۲۰
پس میبینیم که اگر ۲*۱۰=۲۰ با ۲^۱۰=۱۰۲۴ جمع بشه تاثیر چندانی روی نتیجه نهایی نداره(ودرواقع ارزش وقت گذاشتن و اهمیت دادن نداره)
همیشه برای محاسبه پیچیدگی زمانی توی چند جمله ای هایی که عبارات با هم جمع شده اند بالاترین توان را در نظر میگیریم
۰
ارسال: #۴
توابع رشد
به نظر من
[tex]6n^{2} 20n[/tex] از مرتبه [tex]n^{2}[/tex] هست نه [tex]n^{3}[/tex] و اگر اینطور باشه اونوقت عدد گذاریهای شما درست میشه
درواقع باید بگیم که [tex]6n^{2} 20n<=\Omega (n_{3})[/tex] چون حداکثر این عبارتی که نوشتید و یک عبارت خطی از مرتبه ۲ هست
[tex]6n^{2} 20n[/tex] از مرتبه [tex]n^{2}[/tex] هست نه [tex]n^{3}[/tex] و اگر اینطور باشه اونوقت عدد گذاریهای شما درست میشه
درواقع باید بگیم که [tex]6n^{2} 20n<=\Omega (n_{3})[/tex] چون حداکثر این عبارتی که نوشتید و یک عبارت خطی از مرتبه ۲ هست
۰
ارسال: #۵
توابع رشد
۰
ارسال: #۶
توابع رشد
سلام دوست من در مورد [tex]1/lgn[/tex] رو نمی تونی از [tex]n^{2}[/tex] جدا کنی چون در حالت جمع که نیستند چون هر دو یعنی
[tex]n^{2} , 1/lgn[/tex] هر دو به n وابسته و در هم ضرب شده اند میشه [tex]O(n^{2}/lgn)[/tex] اما اگه به صورت
[tex]n^{2} lgn[/tex] بود انگاه جواب شما درسته .
همون طور دوستان گفتن با یک نمونه نمیشه حالا بیا با n=10 حساب کن می بینی غلظه
[tex]n^{2} , 1/lgn[/tex] هر دو به n وابسته و در هم ضرب شده اند میشه [tex]O(n^{2}/lgn)[/tex] اما اگه به صورت
[tex]n^{2} lgn[/tex] بود انگاه جواب شما درسته .
همون طور دوستان گفتن با یک نمونه نمیشه حالا بیا با n=10 حساب کن می بینی غلظه
۰
ارسال: #۷
توابع رشد
[tex]n^{2}/log n <= O(n^{2})[/tex]
نه منظور ما هم خدای نکرده این نبود.خواستیم زیادی توضیح بدیم
ولی باز هم در تقسیم دو عبارت، ما نهایتا بزرگترین توان را به عنوان مرتبه زمانی در نظر میگیریم
درواقع چون بیگ او داریم پس به این معنی هست که باید [tex]n^{2}/log n [/tex] کوچکتر مساوی n^2 باشد و بزرگتر از آن نمیشود (( [tex]n^{2}/log n <= O(n^{2})[/tex] )).درواقع یعنی :"کران بالای تابع [tex]n^{2}/log n <= O(n^{2})[/tex] حداکثر برابر n^2 است" ودیگر تابع ما بیشتر از آن رشد نمیکند
نه منظور ما هم خدای نکرده این نبود.خواستیم زیادی توضیح بدیم
ولی باز هم در تقسیم دو عبارت، ما نهایتا بزرگترین توان را به عنوان مرتبه زمانی در نظر میگیریم
درواقع چون بیگ او داریم پس به این معنی هست که باید [tex]n^{2}/log n [/tex] کوچکتر مساوی n^2 باشد و بزرگتر از آن نمیشود (( [tex]n^{2}/log n <= O(n^{2})[/tex] )).درواقع یعنی :"کران بالای تابع [tex]n^{2}/log n <= O(n^{2})[/tex] حداکثر برابر n^2 است" ودیگر تابع ما بیشتر از آن رشد نمیکند
۰
ارسال: #۸
توابع رشد
سپاس از دوستان
یه سوال دیگه که ترجیح دادم یه تاپیک واسش نزنم و همینجا بپرسم
تعداد mod برای تشحیص دادن اول بودن ۳۷ ایا برابره logn37 هستش ؟ ممنون
یه سوال دیگه که ترجیح دادم یه تاپیک واسش نزنم و همینجا بپرسم
تعداد mod برای تشحیص دادن اول بودن ۳۷ ایا برابره logn37 هستش ؟ ممنون
ارسال: #۹
RE: توابع رشد
(۰۹ اردیبهشت ۱۳۹۱ ۰۲:۳۳ ق.ظ)agha_reza نوشته شده توسط: سپاس از دوستاناگر n فقط بر خودش و یک بخش پذیر باشد عدد اول است حال کد آن را می نویسیم .
یه سوال دیگه که ترجیح دادم یه تاپیک واسش نزنم و همینجا بپرسم
تعداد mod برای تشحیص دادن اول بودن ۳۷ ایا برابره logn37 هستش ؟ ممنون
نقل قول:کد:
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 بار تکرار می شود لذا داریم [tex]O(n)[/tex] و ربطی به [tex]lgn[/tex] ندارد
در مورد n=37 داریم n/2=18 لذا میزان تکرار mod همانا ۱۶ بار است که lg37 =5.2
۰
ارسال: #۱۰
توابع رشد
با سپاس
اما در گزینه ها عدد ۱۶ نیست !
سوال اینه دقیقا : فرض کنیم N=37 ، چه تعداد عملیات mod لازم است تا تعیین شود عدد N اول است ؟
۳۷ -۱۷-۱۸-log37
اما در گزینه ها عدد ۱۶ نیست !
سوال اینه دقیقا : فرض کنیم N=37 ، چه تعداد عملیات mod لازم است تا تعیین شود عدد N اول است ؟
۳۷ -۱۷-۱۸-log37
ارسال: #۱۱
RE: توابع رشد
۰
ارسال: #۱۲
توابع رشد
(n+8)(2n^2 + 2n-4) =O(n^2logn)
این رابطه غلطه چون از سمت چپ تساوی مرتبه ۲n^2 انتخاب میشه که قطعها از n^2 بیشتره ؟
این رابطه غلطه چون از سمت چپ تساوی مرتبه ۲n^2 انتخاب میشه که قطعها از n^2 بیشتره ؟
ارسال: #۱۳
RE: توابع رشد
(۱۳ اردیبهشت ۱۳۹۱ ۰۴:۳۵ ب.ظ)agha_reza نوشته شده توسط: (n+8)(2n^2 + 2n-4) =O(n^2logn)ببین دوست من سمت چپ رو اول باید ضرب کنی بعد اگه ضرب بشه داریم :
این رابطه غلطه چون از سمت چپ تساوی مرتبه ۲n^2 انتخاب میشه که قطعها از n^2 بیشتره ؟
[tex]2n^{3} 18n^{2} 12n-32[/tex]
حالا میشه [tex]O(n^{3})[/tex] واسه این غلطه که [tex]n^{3}>n^{2}lgn[/tex]
۰
ارسال: #۱۵
RE: توابع رشد
۰
ارسال: #۱۶
توابع رشد
صحبت najmedj کاملا درسته ببین دوست من بهتره بری و معنی دقیق علامت های تتا و O بزرگ و کوچک و امگا کوچک و بزرگ رو کامل یاد بگیری اونوقت حل این سوالات برات ساده میشه
در تایید صحبت های قبلی ببین معنی تتا یعنی مقدار دقیق . [tex]\theta (n^{2})[/tex] یعنی دقیق [tex]n^{2}[/tex] نه بیشتر از این مقدار و نه کمتر .
در تایید صحبت های قبلی ببین معنی تتا یعنی مقدار دقیق . [tex]\theta (n^{2})[/tex] یعنی دقیق [tex]n^{2}[/tex] نه بیشتر از این مقدار و نه کمتر .
۰
ارسال: #۱۷
توابع رشد
پیچیدگی زمانی چند جمله ای کدام است ؟
p(n)= 5n^2 +100n+200000
۵n^2
n^2
۱۰۰n
۲۰۰۰۰۰
من میگم گزینه یک
p(n)= 5n^2 +100n+200000
۵n^2
n^2
۱۰۰n
۲۰۰۰۰۰
من میگم گزینه یک
ارسال: #۱۸
RE: توابع رشد
(۱۹ اردیبهشت ۱۳۹۱ ۱۱:۵۱ ب.ظ)agha_reza نوشته شده توسط: پیچیدگی زمانی چند جمله ای کدام است ؟
p(n)= 5n^2 +100n+200000
ضرایب پشت متغیرها اگه ثابت باشند کنار بزارید پیچیدگی میشه [tex]\theta (n^{2} )[/tex]
دلیل :
زمانی که n بزرگ بشه یعنی [tex]n\rightarrow \infty[/tex] بیشترین رو بدون در نظر گرفتن ضرایب ثابت و متغیر های کمتر صحیح است .
متوجه نشدی بازم توضیح بدم
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| جایی برای پیدا کردن توابع آماده جاوااسکریپت | f.b | ۷ | ۴,۵۸۰ |
۲۰ آذر ۱۳۹۹ ۰۴:۰۸ ب.ظ آخرین ارسال: calm |
|
| تعداد توابع پوشا | ss311 | ۰ | ۲,۰۸۵ |
۰۶ بهمن ۱۳۹۸ ۰۴:۵۷ ب.ظ آخرین ارسال: ss311 |
|
 |
مشکل با درک توابع دنباله دار و مولد ؟؟؟؟ | radar | ۰ | ۲,۷۰۵ |
۱۶ دى ۱۳۹۷ ۰۴:۳۶ ب.ظ آخرین ارسال: radar |
| دو سئوال طراحی الگوریتم | java50 | ۱ | ۱,۶۸۷ |
۱۱ اسفند ۱۳۹۵ ۰۱:۱۲ ق.ظ آخرین ارسال: alireza01 |
|
| معنی بهینگی کمتر در توابع هیورستیک | MBe | ۱ | ۲,۰۲۴ |
۰۸ دى ۱۳۹۵ ۰۲:۰۱ ب.ظ آخرین ارسال: Saman |
|
| رشد تابع سینوسی | shamim1395 | ۴ | ۱,۹۴۷ |
۳۰ آذر ۱۳۹۵ ۰۳:۳۸ ب.ظ آخرین ارسال: shamim1395 |
|
| محاسبه رشد تابع | H-Arshad | ۴ | ۳,۹۱۹ |
۱۱ آذر ۱۳۹۵ ۰۴:۳۱ ق.ظ آخرین ارسال: Iranian Wizard |
|
| محاسبه رشد تابع موازی | H-Arshad | ۱ | ۱,۷۰۲ |
۱۰ آذر ۱۳۹۵ ۰۸:۲۱ ق.ظ آخرین ارسال: Jooybari |
|
| نحوه محاسبه درجه رشد | Majiid | ۱ | ۲,۲۸۹ |
۲۷ آبان ۱۳۹۵ ۰۵:۴۵ ب.ظ آخرین ارسال: Behnam |
|
| مقایسه توابع و استفاده از حد | maneshti | ۳ | ۲,۳۰۷ |
۲۴ آبان ۱۳۹۵ ۰۴:۵۷ ب.ظ آخرین ارسال: maneshti |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close