زمان کنونی: ۲۸ آبان ۱۴۰۳, ۰۷:۵۳ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مرتبه و زمان اجرا

ارسال:
  

لهمشد پرسیده:

مرتبه و زمان اجرا

با سلام:
یه سوال تو کتاب اقای یو سفی مطر ح شده که من نمی دونم چطوری میشه ؟
ببنید من این طوری تحلیل کردم ولی هر چقدر فکر میکنم نمی دونم چطوری این نقض مشه ؟
یه سوال دیگه هم دارم و اون اینه: در نماد های مجا نبی c, N0 از چه نو عی هستند منظورم اینه که از لحاظ عددی طبیعی اند یا حقیقی ؟؟


فایل‌(های) پیوست شده


۰
ارسال:
  

۵۴m4n3h پاسخ داده:

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 هست رو معمولاً طبیعی فرض میکنیم اما اگه بخوایم میتونیم حقیقی هم فرضش کنیم!

۰
ارسال:
  

۵۴m4n3h پاسخ داده:

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] برقراره!

۰
ارسال:
  

لهمشد پاسخ داده:

RE: مرتبه و زمان اجرا

ببنید من الان متوجه نمی شم این ۲ تا تابع در چه زمانی هایی با هم فرق دارند
مثلا:
کد:
f(n)=n
g(n)=n^1+sin n
اونوقت این دو تا بع نه O هستند و نه اومگا ؟؟
ولی این تابع رو ببینید ؟
تو همون صفحه ۱۶ تمرین ۱۰ اینطور گفته شده:
کد:
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 استفاده کنید.کتاب یوسفی هم الان پیشم نیست که چک کنم.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

۵۴m4n3h پاسخ داده:

RE: مرتبه و زمان اجرا

مهم فقط این جاست که متوجه بشید sin n هیچ وقت صفر نمیشه! چرا؟ چون که sin فقط توی نقطه هایی مثل [tex]\pi ,2\pi,3\pi,4\pi, ...[/tex] صفر میشه، اما میدونیم که هیچ کدوم از این نقاط عدد طبیعی نیستند، (عدد گنگ هستند) یعنی مطمئنیم که sin n به ازای هیچ عدد طبیعی ای صفر نمیشه و به خاطر حضورش توی قدرمطلق همیشه مثبت هست، پس sin برای [tex]n^2[/tex] یه ضریب مثبت هست!


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
رو نگاه کنید شاید بیشتر متوجه شید!



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  درخواست تصحیح (تعویق) زمان کنکور ارشد ۱۴۰۱ s.gg ۱ ۱۵ ۲۳ بهمن ۱۴۰۱ ۰۷:۴۳ ب.ظ
آخرین ارسال: HamidReza1
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۸۶۳ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  تعویق زمان کنکور ارشد sima84 ۰ ۱,۷۰۶ ۱۸ اردیبهشت ۱۴۰۰ ۰۱:۰۵ ب.ظ
آخرین ارسال: sima84
  زمان جستجوی درخت fateme.sm ۰ ۱,۷۷۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۶۹ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۳۳۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  چگونه این خطا را موقع اجرای sql server 2014 رفع کنم ؟ farahnaz ۲ ۳,۰۴۴ ۱۹ مهر ۱۳۹۹ ۰۲:۱۸ ق.ظ
آخرین ارسال: farahnaz
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۲,۹۴۳ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  اجرای نرم افزار ویندوز در اندروید elecomco ۰ ۳,۰۵۹ ۰۴ خرداد ۱۳۹۹ ۰۸:۳۷ ب.ظ
آخرین ارسال: elecomco
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۴۹۱ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close