با سلام
دوستان فرضا ۵ تا تابع رشد داریم.مثلا یکیش (O(nlong
بعد میگه به ترتیب لیست کنید کدام بدترین و بهترین هست به ترتیب
چه راه حلی به کار برده میشه؟
دو تا دو تا باید با هم مقایسه کنیم؟
(۲۳ آبان ۱۳۹۴ ۰۱:۴۱ ق.ظ)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
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.