۰
subtitle
ارسال: #۱
  
مرتبه و زمان اجرا
با سلام:
یه سوال تو کتاب اقای یو سفی مطر ح شده که من نمی دونم چطوری میشه ؟
ببنید من این طوری تحلیل کردم ولی هر چقدر فکر میکنم نمی دونم چطوری این نقض مشه ؟
یه سوال دیگه هم دارم و اون اینه: در نماد های مجا نبی c, N0 از چه نو عی هستند منظورم اینه که از لحاظ عددی طبیعی اند یا حقیقی ؟؟
یه سوال تو کتاب اقای یو سفی مطر ح شده که من نمی دونم چطوری میشه ؟
ببنید من این طوری تحلیل کردم ولی هر چقدر فکر میکنم نمی دونم چطوری این نقض مشه ؟
یه سوال دیگه هم دارم و اون اینه: در نماد های مجا نبی c, N0 از چه نو عی هستند منظورم اینه که از لحاظ عددی طبیعی اند یا حقیقی ؟؟
۰
ارسال: #۲
  
RE: مرتبه و زمان اجرا
[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 هست رو معمولاً طبیعی فرض میکنیم اما اگه بخوایم میتونیم حقیقی هم فرضش کنیم!
c که حقیقی هست!
n0 هم مهم نیست چی باشه! چون n که سایز ورودی هست رو طبیعی میگیریم n0 رو هم که یه آستانه ای برای n هست رو معمولاً طبیعی فرض میکنیم اما اگه بخوایم میتونیم حقیقی هم فرضش کنیم!
۰
ارسال: #۳
  
RE: مرتبه و زمان اجرا
[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] برقراره!
ریشه های [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] برقراره!
۰
ارسال: #۴
  
RE: مرتبه و زمان اجرا
ببنید من الان متوجه نمی شم این ۲ تا تابع در چه زمانی هایی با هم فرق دارند
مثلا:
اونوقت این دو تا بع نه O هستند و نه اومگا ؟؟
ولی این تابع رو ببینید ؟
تو همون صفحه ۱۶ تمرین ۱۰ اینطور گفته شده:
انگاه
f(n) از مرتبه امگای g(n) هستش ؟ با این فرض که n طبیعی باشد ؟ الان دقیقا متوجه نمیشم چه تفاوتی باعث میشه که تابع اول نه O و نه اومگا باشه ؟ولی تابع دوم امگا می تونه باشه ؟
ممنون[/code]
مثلا:
کد:
f(n)=n
g(n)=n^1+sin n
ولی این تابع رو ببینید ؟
تو همون صفحه ۱۶ تمرین ۱۰ اینطور گفته شده:
کد:
f(n)=|n^2sin n| ,
f(n) از مرتبه امگای g(n) هستش ؟ با این فرض که n طبیعی باشد ؟ الان دقیقا متوجه نمیشم چه تفاوتی باعث میشه که تابع اول نه O و نه اومگا باشه ؟ولی تابع دوم امگا می تونه باشه ؟
ممنون[/code]
ارسال: #۵
  
RE: مرتبه و زمان اجرا
(۲۷ دى ۱۳۸۹ ۰۳:۲۹ ب.ظ)لهمشد نوشته شده توسط: اونوقت این دو تا بع نه 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 استفاده کنید.کتاب یوسفی هم الان پیشم نیست که چک کنم.
۰
ارسال: #۶
  
RE: مرتبه و زمان اجرا
مهم فقط این جاست که متوجه بشید sin n هیچ وقت صفر نمیشه! چرا؟ چون که sin فقط توی نقطه هایی مثل [tex]\pi ,2\pi,3\pi,4\pi, ...[/tex] صفر میشه، اما میدونیم که هیچ کدوم از این نقاط عدد طبیعی نیستند، (عدد گنگ هستند) یعنی مطمئنیم که sin n به ازای هیچ عدد طبیعی ای صفر نمیشه و به خاطر حضورش توی قدرمطلق همیشه مثبت هست، پس sin برای [tex]n^2[/tex] یه ضریب مثبت هست!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
رو نگاه کنید شاید بیشتر متوجه شید!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
رو نگاه کنید شاید بیشتر متوجه شید!
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close