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

نسبت مرتبه زمانی دو تابع به یک دیگر Big-Oh است آنگاه....

ارسال:
  

sMohammad پرسیده:

نسبت مرتبه زمانی دو تابع به یک دیگر Big-Oh است آنگاه....

سلام
تو عکس اول گزینه ۲ رو مورد بحث هست. سوال گفته که مرتبه زمانی تابع f کوچتر مساوی (کوچکتر یا مساوی) مرتبه زمانی تابع g هست. با این شرط، میشه گفت اگر یک عدد ثابت (مثل ۲) بیاریم و این دو رو جای توان این عدد ثابت قرار بدیم، باز هم رابطه Big-Oh بینشون برقراره؟
خب، گقته رشد f کوچتر مساوی رشد g باشه الان با این مثال نقضی که آورده، f(n)=2n و g(n)=n شرط رو که رعایت نکرده. درسته هر دو تابع جمله تاثیر گذار در مرتبه زمانیشون که n هست، توانش ۱ هست، ولی خب مشخصه که اگر به هر دو یک مقدار بدیم (مثلا n=2) تابع f=4 و تابع g=2 میشه و اگر بدیم n=4 تابع f=8 و تابع g=4 میشه. خب الان رشد f بیشتر از g شده، پس شرط سوال رو رعایت نکرده چون f باید کوچکتر مساوی g باشه، الان بزرگتر مساوی شد.
عکس اول:



باز هم همین مورد در عکس دوم برای گزاره ۳ مد نظر هست
عکس دوم:

نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Saman پاسخ داده:

RE: نسبت مرتبه زمانی دو تابع به یک دیگر Big-Oh است آنگاه....

سلام.
در مثال اول شرط رعایت شده چون به هر حال به ازای یک C مقدار تابع رو میشه برقرار کرد.اما تاثیر همین مقدار C در توان خیلی بیشتر هست.

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

یه نگاه دیگه به تعاریف ریاضی این order ها بندازید حتما.

شما اومدید به جای مرتبه ی زمانی مقادیر ثابت C گذاشتید.نه این اشتباه هستش. توابع شما به این شکل هستند :

مثلا :
[tex]f(n)=C(n)\: ,\: g(n)=C(n)[/tex] حالا فقط C ها رو میتونید دستکاری کنید و مرتبه زمانی رو بسنجید.

شما زمانی که در دو مورد بالا C ها رو دستکاری میکنی تمام کارتون توی مرتبه ی n هست، اما وقتی این ها رو به توان میبرید درواقع دارید مرتبه ی نمایی رو دستکاری میکنید. دستکاری مرتبه ی نمایی به اندازه ی [tex]\varepsilon[/tex] مرتبه رو به شدت افزایش میدهد
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۴۲ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۴۳۹ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
Heart هزینه عشق واقعی چقدر است aatwo ۵ ۵,۳۰۹ ۱۳ بهمن ۱۳۹۹ ۱۰:۱۴ ب.ظ
آخرین ارسال: ghaderZ
  نسبت راست دو زبان fly2000 ۰ ۱,۱۷۷ ۰۲ آبان ۱۳۹۹ ۰۱:۱۵ ق.ظ
آخرین ارسال: fly2000
  نسبت راست دو زبان fly2000 ۰ ۱,۱۲۱ ۰۲ آبان ۱۳۹۹ ۰۱:۱۴ ق.ظ
آخرین ارسال: fly2000
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۴ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  چجوری بفهمیم سرور hp اورجینال است یا خیر!؟ azade1992 ۱ ۲,۲۱۶ ۰۳ مهر ۱۳۹۹ ۱۰:۵۹ ق.ظ
آخرین ارسال: diiyan
  کدام زبان برنامه‌نویسی بهترین انتخاب است؟ elecomco ۲ ۲,۷۳۴ ۱۰ شهریور ۱۳۹۹ ۰۵:۱۶ ب.ظ
آخرین ارسال: kilookiloo
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۲۰۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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