۰
subtitle
ارسال: #۱
  
محدود به چندجمله ای یعنی چه؟
سلام.
در بعضی مسائل منظور از اینکه گفته میشود بررسی نمایید که آیا [tex]f(n)[/tex] محدود به چندجمله ای است یا نه چیست؟لطفا یک مثال هم بیاورید. با تشکر
در بعضی مسائل منظور از اینکه گفته میشود بررسی نمایید که آیا [tex]f(n)[/tex] محدود به چندجمله ای است یا نه چیست؟لطفا یک مثال هم بیاورید. با تشکر
۰
ارسال: #۲
  
RE: محدود به چندجمله ای یعنی چه؟
اگر تابع 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]
اگر[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]
۰
ارسال: #۳
  
RE: محدود به چندجمله ای یعنی چه؟
(۰۱ بهمن ۱۳۸۹ ۰۱:۳۸ ب.ظ)sos006 نوشته شده توسط: سلام.ای شیطون معلومه بچه خوبی نیستی و درسات رو به موقع نمی خونی
در بعضی مسائل منظور از اینکه گفته میشود بررسی نمایید که آیا [tex]f(n)[/tex] محدود به چندجمله ای است یا نه چیست؟لطفا یک مثال هم بیاورید. با تشکر
![Tongue Tongue](images/smilies/tongue.gif)
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close