سلام
تو عکس اول گزینه ۲ رو مورد بحث هست. سوال گفته که مرتبه زمانی تابع 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 باشه، الان بزرگتر مساوی شد.
عکس اول:
[attachment=20839]
باز هم همین مورد در عکس دوم برای گزاره ۳ مد نظر هست
عکس دوم:
[attachment=20840]
سلام.
در مثال اول شرط رعایت شده چون به هر حال به ازای یک C مقدار تابع رو میشه برقرار کرد.اما تاثیر همین مقدار C در توان خیلی بیشتر هست.
شما به ازای یک مقدار اپسیلون تابعت رشدش نمایی میشه.
یه نگاه دیگه به تعاریف ریاضی این order ها بندازید حتما.
شما اومدید به جای مرتبه ی زمانی مقادیر ثابت C گذاشتید.نه این اشتباه هستش. توابع شما به این شکل هستند :
مثلا :
[tex]f(n)=C(n)\: ,\: g(n)=C(n)[/tex] حالا فقط C ها رو میتونید دستکاری کنید و مرتبه زمانی رو بسنجید.
شما زمانی که در دو مورد بالا C ها رو دستکاری میکنی تمام کارتون توی مرتبه ی n هست، اما وقتی این ها رو به توان میبرید درواقع دارید مرتبه ی نمایی رو دستکاری میکنید. دستکاری مرتبه ی نمایی به اندازه ی [tex]\varepsilon[/tex] مرتبه رو به شدت افزایش میدهد