به نظرم میشه ۱ تابع ولی کلید ۳ هستش
مگه n^2log^2 بزرگتر از n^2 نیست پس چرا هم مرتبه گرفته ؟
همین طور n^2
![[تصویر: Big0.jpg]](http://dl.dropboxusercontent.com/u/73158448/Question/Day_5/Big0.jpg)
به نظر منم همون سه تا میشه آخه مگه نه اینه که ۹T(n/3) با f مقایسه میشه اگه اولی بزگتر باشه مرتبه T میشه n^2 اگه دومی (f) بزرگتر باشه مرتبه Tمیشه همون f(n) و اگه مساوی باشن میشه n^2logn بنابر قضیه اصلی پس در هر صورت از n^2 بزرگتره. بنابراین اگه g(n) =n^3 انتخاب بشه می تونیم f(n) رو یه تابع مثلا همون n^3 بدیم اما اگه n^2log^2n باشه می تونیم f رو همون بگیریم و همچنین برای g برابر با n^2 می تونیم f رو یه تابع کمتر از n^2 بگیریم که به خاطر وجود ۹T(n/3) مرتبه میشه n^2 اما برای g(n)= nlogn هر کاری بکنیم و هر تابعی برای f انتخاب کنیم، مرتبه حداقل n^2 هست.
.
من میگم ضرب یک تابع در lgn مرتبه شو بزرگتر میکنه نه اینکه هنوز هم مرتبه باشند.
اینطور نیست؟
(۲۹ دى ۱۳۹۱ ۰۵:۱۶ ب.ظ)egm1176 نوشته شده توسط: ضرب یک تابع در lgn مرتبه شو بزرگتر میکنه نه اینکه هنوز هم مرتبه باشند.بله درسته.
خب این که طبق پاسخ سوال که گزینه ۳ هستش که مغایرتی نداره!
هنوز ابهامی هست؟
من از یکی از دوستام که پرسیدم گفت تو صورت سوال رو متوجه نشدی.
ببینید من اینجوری فهمیدم :
سوال گفته هر کدام از این تابع های g رو بذار جای f و T رو پیدا کن . بعد ببین آیا T و G هم مرتبه هستند یا نه ؟
درسته ؟!
(۲۹ دى ۱۳۹۱ ۰۵:۴۱ ب.ظ)egm1176 نوشته شده توسط: سوال گفته هر کدام از این تابع های g رو بذار جای f و T رو پیدا کن . بعد ببین آیا T و G هم مرتبه هستند یا نه ؟آره egm1176 عزیز...
درسته ؟!
خیلی ممنونم. خیالم راحت شد...
پس حالا من میام n^2logn رو میذارم به جای f و مرتبه تابع میشه n^2log^2n که از f یا همون g بزرگتره و هم مرتبه اش نیست.
همین طور در مورد n^2 و nlogn
من میگم فقط n^3 صدق میکنه.
سوال گفته هر کدام از این تابع های g رو بذار جای f و T رو پیدا کن . بعد ببین آیا T و G هم مرتبه هستند یا نه ؟
درسته ؟!!!!!
شما مطلب من رو خوندید؟ خواهشمندم یکم با دقت تر بخونین. کجای سوال گفته g را بجای f بگذارین و T رو حساب کنین. اگه این طور بود حرف شما درسته ولی سوال اصلا منظورش این نبوده.ببینید من دوباره به صورت واضح براتون توضیح میدم
سوال گفته آیا می توان دست کم یک تابع f ای پیدا کرد که اگر آن را در مساله قرار داد و مرتبه زمانی T را حساب کرد برابر با g شود. خوب اول از همه اگر g =n^3 باشد به دنبال f می گردیم که اگر در مساله قرار گیرد T بشود n^3 خوب با چه f ای می توان این کار را کرد با f=n^3 حالا شما اگه T را محاسبه کردید می شود همان g یعنی n^3 بنابر قضیه اصلی چونf=n^3 بزرگتر از n^log(9,3) است.
حال اگر T=n^2log^2n باشد می توان f را n^2logn درنظر گرفت (یعنی f ای پیدا می شود)تا T=g شود.
و برایf T=n^2 می شود تابعی کمتر از n^2 مثلا n چون اگر f=n باشد در آن صورت T=9T(n/3)+n که می شود همان T=n^2=g
اما برای آنکه T=nlogn شود هیچ تابع f ای نمی توان پیدا کرد.
به نظرم توضیح کافی بود
بله بله...
حالا متوجه شدم
خیلی خیلی ممنونم !
گاهی تو فهم سوالا اینجوری گیر میکنم!
