سلام.
در بعضی مسائل منظور از اینکه گفته میشود بررسی نمایید که آیا [tex]f(n)[/tex] محدود به چندجمله ای است یا نه چیست؟لطفا یک مثال هم بیاورید. با تشکر
(۰۱ بهمن ۱۳۸۹ ۰۱:۳۸ ب.ظ)sos006 نوشته شده توسط: سلام.ای شیطون معلومه بچه خوبی نیستی و درسات رو به موقع نمی خونی
در بعضی مسائل منظور از اینکه گفته میشود بررسی نمایید که آیا [tex]f(n)[/tex] محدود به چندجمله ای است یا نه چیست؟لطفا یک مثال هم بیاورید. با تشکر
. دوست عزیز یه نگاه به این لینک بنداز !!! (شوخی کردم حالت سر جا بیاد و انرژیت زیاد شه)مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
اگر تابع f یک چندجمله ای محدود باشه باید حتما یک c و k که اعداد ثابتی هستند وجود داشته باشه که:
اگر[tex]f\left( n \right )\leq c n^{k}[/tex]
آنگاه باید نتیجهی زیر برقرار باشه:
[tex]\lg \left( f\left( n \right )\right )\leq kc\lg n[/tex]
و در نتیجه: [tex]\lg \left( f\left( n \right )\right )= O\left( \lg \left( n \right )\right )[/tex]
مثلا تابع [tex]f\left( n \right )= \left \lceil \lg n \right \rceil![/tex]
بدلیل زیر محدود نیست:
[tex]\lg \left( \left \lceil \lg n \right \rceil! \right )=\theta \left( \left \lceil \lg n \right \rceil\lg \left \lceil \lg n \right \rceil \right )= \theta \left( \lg n\lg \lg n \right )= \omega \left( \lg n \right )\neq O\left( \lg n \right )[/tex]