۰
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] محدود به چندجمله ای است یا نه چیست؟لطفا یک مثال هم بیاورید. با تشکر
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close