سلام دوستان
توی یک جزوه به یک مطلبی بر خوردم
می خواستم نظر شما رو بدونم
نظر شما در مورد درستی و نادرستی دو عبارت زیر چیه؟؟
با سلام دوست عزیز گزینه یک غلط هست ولی گزینه ۲ درسته ببینید با یک مثال توضیح میدهم
فرض کنیم
[tex]f(n)\: =\: 2n^2[/tex]
خوب این تابع شما قبول دارید که O (big) مجموعه زیر هست
[tex]\{n^2,n^3,2^n,3^n,n^n\}\: [/tex]
حالا قبول دارید که تابع از مرتبه o (small) مجموعه زیر هستش
[tex]\{n^3,2^n,3^n,n^n\}\: [/tex]
چرا؟ چون ما توی تعریف big o داریم که به ازای یک c شرط برقرار باشه یا در واقع همون حرف که میگیم رشد تابع g بزرگتر مساوی رشد f باشه
در حالی که توی تعریف small o میگیم به ازای هر c باید شرط برقرار باشه نه یک c بلکه هر c بگیریم باید برقرار باشه یعنی همون حرف که میگه رشد g باید بزرگتر از رشد f باشه یعنی نمی تونن هم رشد باشن
خوب پس این دوتا مجموعه حالا قیاس کنید کدوم می تونه زیر مجموعه اون یکی باشه؟ پس گزینه ی دو درسته و گزینه یک غلط هستش
اگر لازم هست تا توضیح بیشتری بدهم
موفق باشید
ممنون از پاسختون
من هم کاملا با شما هم عقیده هستم
اما توی جروه ای دارم میبینم که اثبات کرده که هر دو درست هستند!!!!
البته اثباتش قابل فهم نیست و متوجه نمیشم!!!
در نهایت به این نتیجه رسیده که هر دو مجموعه بالا هم ارز هستند
اینکه چطوری به این نتیجه رسیده را بهتره بزارید تا دوستان نظر بدهند
ولی در حالت کلی شرط یک غلط هست و تعریف مجانب ها نقض میشه حالا چطوری میگه هم ارز هستن من نمیدونم ولی در حالت خاص که در واقع ما اون [tex]n^2[/tex]
از مجموعه big o حذف کنیم میشه گفت هم ارز هستن چون دوتا مساوی میشن و میدونیم هر مجموعه زیر مجموعه خودشه و درسته ولی در حالت کلی هم ارز نیستن البته تا اونجای که من خوندم و می دونم حالا شاید حرف یا اثبات ایشون درسته و من دارم اشتباه می کنم شاید بهتر باشه بقیه هم نظراتشونو اعلام کنن
موفق باشید
اینم اثباتی که نوشته