زمان کنونی: ۲۷ شهریور ۱۳۹۸, ۰۳:۴۴ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

کدام راه حل مناسب است؟

ارسال:
  

H-Arshad پرسیده:

کدام راه حل مناسب است؟

با سلام
دوستان فرضا ۵ تا تابع رشد داریم.مثلا یکیش (O(nlong
بعد میگه به ترتیب لیست کنید کدام بدترین و بهترین هست به ترتیب
چه راه حلی به کار برده میشه؟
دو تا دو تا باید با هم مقایسه کنیم؟
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Pure Liveliness پاسخ داده:

RE: کدام راه حل مناسب است؟

(۲۳ آبان ۱۳۹۴ ۰۱:۴۱ ق.ظ)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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کدام سوالات ۶۰۰ مساله در ارشد مطرح شدند ؟ Happiness.72 ۲ ۴۳۸ ۱۸ فروردین ۱۳۹۶ ۰۳:۴۶ ب.ظ
آخرین ارسال: Happiness.72
  آیا راه حل حریصانه دارند؟ maneshti ۴ ۵۹۶ ۰۶ دى ۱۳۹۵ ۰۲:۵۱ ب.ظ
آخرین ارسال: Jooybari
Photo کران مناسب مرتب سازی ziba.O ۶ ۱,۲۲۸ ۰۸ بهمن ۱۳۹۳ ۱۱:۲۲ ق.ظ
آخرین ارسال: ziba.O
  راه حل سوال گراف ایتی ۹۲ tanhatarin ۰ ۶۳۸ ۲۱ دى ۱۳۹۳ ۰۲:۳۷ ب.ظ
آخرین ارسال: tanhatarin
  تحلیل راه حل سومین کوچکترین عنصر NP-Cσмρℓєтє ۶ ۱,۲۳۶ ۲۰ دى ۱۳۹۳ ۰۷:۴۷ ب.ظ
آخرین ارسال: shayesteb
Question رابطه بازگشتی؛ حل از کدام روش؟ Ametrine ۱۲ ۲,۱۸۵ ۱۷ دى ۱۳۹۳ ۰۱:۱۱ ب.ظ
آخرین ارسال: Ametrine
  پیچیدگی زمانی این تابع چقدر است؟ T(n)=T(sqrt n)+1 sipser ۲ ۹۹۴ ۲۷ آذر ۱۳۹۳ ۱۲:۳۵ ب.ظ
آخرین ارسال: so@
Question کدام ویژگی لگاریتم A.I ۱۲ ۱,۵۴۴ ۲۳ مرداد ۱۳۹۳ ۱۰:۰۸ ب.ظ
آخرین ارسال: نازین
  الگوریتم مناسب برای یافتن دو عنصر از ارایه که مجموع مقادیرشان برابر x است fulgent ۱۲ ۳,۱۵۴ ۱۳ اسفند ۱۳۹۲ ۱۰:۰۹ ب.ظ
آخرین ارسال: arshad90
  آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟ masoud67 ۱۹ ۴,۳۶۹ ۰۹ بهمن ۱۳۹۲ ۰۹:۱۹ ب.ظ
آخرین ارسال: hoomanab

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close