تالار گفتمان مانشت
سوال ۲۰ فصل ۱ ساختمان پوران چاپ ۸۹ ( آی تی ۸۴) مربوط به پیچیدگی - نسخه‌ی قابل چاپ

سوال ۲۰ فصل ۱ ساختمان پوران چاپ ۸۹ ( آی تی ۸۴) مربوط به پیچیدگی - ttiiko - 19 شهریور ۱۳۹۲ ۰۶:۳۵ ب.ظ

عارضم به خدمتتون که مرحمت کنید راهنمایی بفرمایید که بنده در سوال ۲۰ ساختمان پوران فصل ۱ چاپ ۸۹ کجا رو دارم اشتباه می کنم :

کدام صحیح است؟

[tex]n^{2} sin n \epsilon \Omega (n)[/tex]

جواب : اگر n طبیعی فرض شود آنگاه n^2 sin n >=Cn به ازای حداقل یک C , n0 مثبت و همه n>=n0 صحیح است... پایان جواب .

خب اگه n را بزاریم ۱۸۱ که سینوس منفی میشه اونوقت برای n های قبل و بعد ۱۸۰ دو C مختلف العلامت میخوایم که خب نمیشه که....؟

RE: سوال ۲۰ فصل ۱ ساختمان پوران چاپ ۸۹ ( آی تی ۸۴) مربوط به پیچیدگی - amin222 - 24 شهریور ۱۳۹۲ ۰۹:۴۳ ق.ظ

دوست عزیز سلام
ابهامتون کاملا درست و فکر کنم با سوالتون به نکته خوبی اشاره کردید که گاهی میبینیمش و سرسری از کنارش رد میشیم این نکته هم تو تعریف نمادهای مجانبی اومده به عنوان نمونه به تعریف [tex]f(n)=\Omega (g(n))[/tex] دقت کنید

[tex]\Omega(g(n))=f(n):\exists c,n0>0 , \forall n\geqslant n0 :{\color{Red} 0\leq cg(n)\leq f(n)}[/tex]

اون قسمتی که قرمز کردم میگیه جوابهای تابع ما باید بزرگتر از صفر بوده و منفی نباشد و این یعنی اینکه جوابی که دادن درسته و تعریف نمادهای مجانبی منفی شدن تابع رو قبول نمیکنه