با سلام:
یه سوال تو کتاب اقای یو سفی مطر ح شده که من نمی دونم چطوری میشه ؟
ببنید من این طوری تحلیل کردم ولی هر چقدر فکر میکنم نمی دونم چطوری این نقض مشه ؟
یه سوال دیگه هم دارم و اون اینه: در نماد های مجا نبی c, N0 از چه نو عی هستند منظورم اینه که از لحاظ عددی طبیعی اند یا حقیقی ؟؟
[tex]f(n)=\Theta (f(\frac{n}{2}))[/tex] در حالت کلی غلط هست و یه مثال نقضش میتونه [tex]f(n)=4^{n}[/tex] باشه که مرتبه اش از [tex]f(\frac{n}{2})=2^{n}[/tex] بیشتر هست و هم مرتبه نیستند!
c که حقیقی هست!
n0 هم مهم نیست چی باشه! چون n که سایز ورودی هست رو طبیعی میگیریم n0 رو هم که یه آستانه ای برای n هست رو معمولاً طبیعی فرض میکنیم اما اگه بخوایم میتونیم حقیقی هم فرضش کنیم!
ببنید من الان متوجه نمی شم این ۲ تا تابع در چه زمانی هایی با هم فرق دارند
مثلا:
کد:
f(n)=n
g(n)=n^1+sin nولی این تابع رو ببینید ؟
تو همون صفحه ۱۶ تمرین ۱۰ اینطور گفته شده:
کد:
f(n)=|n^2sin n| ,f(n) از مرتبه امگای g(n) هستش ؟ با این فرض که n طبیعی باشد ؟ الان دقیقا متوجه نمیشم چه تفاوتی باعث میشه که تابع اول نه O و نه اومگا باشه ؟ولی تابع دوم امگا می تونه باشه ؟
ممنون[/code]
(۲۷ دى ۱۳۸۹ ۰۳:۲۹ ب.ظ)لهمشد نوشته شده توسط: اونوقت این دو تا بع نه O هستند و نه اومگا ؟؟
[tex]If \; sin(n)=-0.1 \Rightarrow g(n)=n^{0.9}[/tex]
[tex]If \; sin(n)=0.1 \Rightarrow g(n)=n^{1.1}[/tex]
در نتیجه با توجه به اینکه نمی دونیم [tex]sin(n)[/tex] مقدارش مثبت میشه یا منفی ،نمی تونیم دو تابع را با هم مقایسه کنیم.
مثال دومتون واضح نیست. بهتره که برای نوشتن توابع از Tex استفاده کنید.کتاب یوسفی هم الان پیشم نیست که چک کنم.
[tex]\left | n^2 sin n \right | = n^2 \left | sin n \right |[/tex]
ریشه های [tex]sin n[/tex] برابر هست با [tex]n=k\pi[/tex] اگه n رو طبیعی فرض کنیم از اون جایی که [tex]\pi[/tex] عدد گنگ هست، [tex]sin n[/tex] هیچ وقت در نقاط صحیح صفر نمیشه یعنی هیچ nی که طبیعی باشه صفرش نمیکنه؛ چون توی قدر مطلق هست منفی هم نمیشه! پس [tex]n^2|sin n| = c n^2[/tex] که c > 0 هست. پس رابطه‌ی [tex]|n^2sin n| = \Omega (n)[/tex] برقراره!
مهم فقط این جاست که متوجه بشید sin n هیچ وقت صفر نمیشه! چرا؟ چون که sin فقط توی نقطه هایی مثل [tex]\pi ,2\pi,3\pi,4\pi, ...[/tex] صفر میشه، اما میدونیم که هیچ کدوم از این نقاط عدد طبیعی نیستند، (عدد گنگ هستند) یعنی مطمئنیم که sin n به ازای هیچ عدد طبیعی ای صفر نمیشه و به خاطر حضورش توی قدرمطلق همیشه مثبت هست، پس sin برای [tex]n^2[/tex] یه ضریب مثبت هست!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
رو نگاه کنید شاید بیشتر متوجه شید!