(۲۳ آبان ۱۳۹۴ ۰۱:۴۱ ق.ظ)H-Arshad نوشته شده توسط:  با سلام
دوستان فرضا ۵ تا تابع رشد داریم.مثلا یکیش (O(nlong
بعد میگه به ترتیب لیست کنید کدام بدترین و بهترین هست به ترتیب
چه راه حلی به کار برده میشه؟
دو تا دو تا باید با هم مقایسه کنیم؟

سلام.قانون کلی وجود نداره خب. به هر حال:
اول از همه یک سری توابع رو ساده سازی میکنیم. مثل تابع n= ۲^ logn
بعضی توابع که میدن خیلی واضح هست رشدش از بقیه کمتره، مثلا ممکنه همه شون صعودی باشن، یکی نزولی.
بعضی توابع که رشدشون مساوی هست و یکی شون که برامون قابل درک تر و راحت تر هست رو با بقیه مقایسه میکنیم.
راجع به بقیه هم شبیه اون جدول مقایسه ی state ها توی نظریه( که میخواستیم ببینیم میشه ادغامشون کرد یا نه) مقایسه رو انجام میدیم. در کل توی تست ها که کار راحت تر هست و مقایسه میکنیم فقط.
مثلاََ تست شماره ی ۳۲.۱ کتاب ۶۰۰ مساله ی دکتر قدسی:
log*n مقدار کوچیکی هست، حتی برای عددای خیلی بزرگ میشه ۶، ۲ به توانش هم مقدار کوچیکی هست، اندازه ی یه عدد ثابت، تابع نزولی هم نداریم این جا، پس g6 از همه کوچیکتره.
g5 رو ساده کنیم میشه n^1/2 که از g4 کمتره. تا این جا:
g6<.... <g5<...<g4
تابع نمایی با پایه ی بزرگتر از یک از چند جمله ای رشدش بیشتره، یعنی g1 از g4 و g5 رشدش بیشتره. حالا تا این جا می دونیم:
g6< ...< g5<...<g4<...< g1
حالا دو تا تابع داریم که توی این سه تا جای خالی قرار میگیرن، شایدم پشت هم. تابع g3 و g2 مونده، g2 از g3 کمتره. از طرفی اینا هر دو از g5 بیشتر هستن، این واضح هست. تا این جا:
g6< g5<....<g4<...< g1
با g4 مقایسه میکنیم و تموم. خب اینم واضح هست که g4 از این دو تا کمتره. پس:
g6< g5<g4<g2<g3< g1

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