۰
subtitle
ارسال: #۱
  
مرتبه زمانی - کنکور ۸۶
کامپیوتری در واحد زمان مساله ای به اندازه ۱۶ را که الگوریتم آن از مرتبه زمانی [tex]n2^n[/tex] است حل میکند، اگر سرعت کامپیوتر ۱۳۱۰۷۲ برابر گردد این کامپیوتر همان مساله را با چه اندازه ای در واحد زمان حل خواهد کرد؟
لطفاً کامل توضیح بدید، از اول اولش : )
لطفاً کامل توضیح بدید، از اول اولش : )
۴
ارسال: #۲
  
RE: مرتبه زمانی - کنکور ۸۶
وقتی می گن یک مسله باسیز۱۶ با پیچیدگی [tex]n2^n[/tex]یعنی این که پیچیدگی این مسئله [tex]16\ast2^{16}[/tex] است.
خب این مسئله را در یک واحد زمان حل می کنه
پس سرعت کامپیوتر چقدر است که مسئله را با سایز [tex]16\ast2^{16}[/tex] را در ۱ واحد زمان حل می کند؟
اگر سرعت را با rate سایز مسئله را با size و زمان را با time نشان دهیم از این راه سرعت کامپیوتر را بدست می آوریم [tex](\frac{size}{rate}=time)[/tex])چرا ؟ چون هر چه سرعت بیشتر باشد زمان کمتر و هر چه سایز بیشتر باشد زمان بیشتری مصرف می شود پس سایز با زمان رابطه مستقیم و سرعت با زمان رابطه عکس دارد.
[tex](\frac{16\ast2^{16}}{rate}=1)[/tex]
پس سرعت برابر است با:[tex](rate=16\ast2^{16})[/tex]
حالا وقتی می گوید سرعت را ۱۳۱۰۷۲ برابر کرده ایم یعنی این که سرعت را عملا بیشتر کرده ایم
پس سرعت جدید می شود: [tex](rate=16\ast2^{16}\ast131072=2^4\ast2^{16}\ast2^{17}=2^{37})[/tex]
می خواهیم ببینیم با این سرعت جدید مسئله با چه سایزی را در زمان واحد حل می کنیم پس سایز مجهول است:
[tex]\frac{size}{2^{37}}=1[/tex]
[tex]n2^n=2^{37}[/tex]
[tex]n2^n=32\ast2^{32}[/tex]
پس سایز مسئله ۳۲ است.
خب این مسئله را در یک واحد زمان حل می کنه
پس سرعت کامپیوتر چقدر است که مسئله را با سایز [tex]16\ast2^{16}[/tex] را در ۱ واحد زمان حل می کند؟
اگر سرعت را با rate سایز مسئله را با size و زمان را با time نشان دهیم از این راه سرعت کامپیوتر را بدست می آوریم [tex](\frac{size}{rate}=time)[/tex])چرا ؟ چون هر چه سرعت بیشتر باشد زمان کمتر و هر چه سایز بیشتر باشد زمان بیشتری مصرف می شود پس سایز با زمان رابطه مستقیم و سرعت با زمان رابطه عکس دارد.
[tex](\frac{16\ast2^{16}}{rate}=1)[/tex]
پس سرعت برابر است با:[tex](rate=16\ast2^{16})[/tex]
حالا وقتی می گوید سرعت را ۱۳۱۰۷۲ برابر کرده ایم یعنی این که سرعت را عملا بیشتر کرده ایم
پس سرعت جدید می شود: [tex](rate=16\ast2^{16}\ast131072=2^4\ast2^{16}\ast2^{17}=2^{37})[/tex]
می خواهیم ببینیم با این سرعت جدید مسئله با چه سایزی را در زمان واحد حل می کنیم پس سایز مجهول است:
[tex]\frac{size}{2^{37}}=1[/tex]
[tex]n2^n=2^{37}[/tex]
[tex]n2^n=32\ast2^{32}[/tex]
پس سایز مسئله ۳۲ است.
ارسال: #۳
  
RE: مرتبه زمانی - کنکور ۸۶
(۲۳ مهر ۱۳۹۳ ۱۰:۰۰ ق.ظ)fatemeh69 نوشته شده توسط: وقتی می گن یک مسله باسیز۱۶ با پیچیدگی [tex]n2^n[/tex]یعنی این که پیچیدگی این مسئله [tex]16\ast2^{16}[/tex] است.تشکر، فقط آخرش چطوری n رو بدست میاریم؟ چطوری ۳۲ میشه؟
خب این مسئله را در یک واحد زمان حل می کنه
پس سرعت کامپیوتر چقدر است که مسئله را با سایز [tex]16\ast2^{16}[/tex] را در ۱ واحد زمان حل می کند؟
اگر سرعت را با rate سایز مسئله را با size و زمان را با time نشان دهیم از این راه سرعت کامپیوتر را بدست می آوریم [tex](\frac{size}{rate}=time)[/tex])چرا ؟ چون هر چه سرعت بیشتر باشد زمان کمتر و هر چه سایز بیشتر باشد زمان بیشتری مصرف می شود پس سایز با زمان رابطه مستقیم و سرعت با زمان رابطه عکس دارد.
[tex](\frac{16\ast2^{16}}{rate}=1)[/tex]
پس سرعت برابر است با:[tex](rate=16\ast2^{16})[/tex]
حالا وقتی می گوید سرعت را ۱۳۱۰۷۲ برابر کرده ایم یعنی این که سرعت را عملا بیشتر کرده ایم
پس سرعت جدید می شود: [tex](rate=16\ast2^{16}\ast131072=2^4\ast2^{16}\ast2^{17}=2^{37})[/tex]
می خواهیم ببینیم با این سرعت جدید مسئله با چه سایزی را در زمان واحد حل می کنیم پس سایز مجهول است:
[tex]\frac{size}{2^{37}}=1[/tex]
[tex]n2^n=2^{37}[/tex]
[tex]n2^n=32\ast2^{32}[/tex]
پس سایز مسئله ۳۲ است.
ارسال: #۴
  
RE: مرتبه زمانی - کنکور ۸۶
(۲۳ مهر ۱۳۹۳ ۰۳:۵۹ ب.ظ)Ametrine نوشته شده توسط: تشکر، فقط آخرش چطوری n رو بدست میاریم؟ چطوری ۳۲ میشه؟
باید [tex]2^{37}[/tex]رو به فرم [tex]n2^n[/tex] بنویسیم
چند بار امتحان می کنیم ببینیم باید چجوری دو به توان ۳۷ رو خورد کرد که به این فرم دربیاد واضحه که عددمون باید از ۱۶ بیشتر باشه (چون خود ورودی اولیه مسئله ۱۶ بود و حالا که سرعت رو بیشتر کردیم باید ورودی بزرگتری را در زمان واحد حل کنه)
از طرفی می دونیم که دو به توان ۳۷ رو اگه بخواهیم بشکونیم و دو قسمتش کنیم هر دو قسمت توانی از دو هست خب چی از ۱۶ بزرگتره وتوانی از دو هست؟ ۳۲
[tex]2^{37}=n2^n=2^{37-n}2^n=2^52^{32}=32\ast2^{32}[/tex]
البته ممکن بود ۳۲ هم جور در نیاد یعنی ۳۲ ضرب در دو به توان ۳۲ ممکن بود هنوز کوچکتر از عدد دو به توان ۳۷ باشهاگه این اتفاق می افتاد ۶۴ و ۱۲۸ و ... را امتحان می کردیم.
ارسال: #۵
  
RE: مرتبه زمانی - کنکور ۸۶
(۲۴ مهر ۱۳۹۳ ۰۴:۳۱ ب.ظ)fatemeh69 نوشته شده توسط:تشکر ، فکر کردم روش خاصی داره!(23 مهر ۱۳۹۳ ۰۳:۵۹ ب.ظ)Ametrine نوشته شده توسط: تشکر، فقط آخرش چطوری n رو بدست میاریم؟ چطوری ۳۲ میشه؟
باید [tex]2^{37}[/tex]رو به فرم [tex]n2^n[/tex] بنویسیم
چند بار امتحان می کنیم ببینیم باید چجوری دو به توان ۳۷ رو خورد کرد که به این فرم دربیاد واضحه که عددمون باید از ۱۶ بیشتر باشه (چون خود ورودی اولیه مسئله ۱۶ بود و حالا که سرعت رو بیشتر کردیم باید ورودی بزرگتری را در زمان واحد حل کنه)
از طرفی می دونیم که دو به توان ۳۷ رو اگه بخواهیم بشکونیم و دو قسمتش کنیم هر دو قسمت توانی از دو هست خب چی از ۱۶ بزرگتره وتوانی از دو هست؟ ۳۲
[tex]2^{37}=n2^n=2^{37-n}2^n=2^52^{32}=32\ast2^{32}[/tex]
البته ممکن بود ۳۲ هم جور در نیاد یعنی ۳۲ ضرب در دو به توان ۳۲ ممکن بود هنوز کوچکتر از عدد دو به توان ۳۷ باشهاگه این اتفاق می افتاد ۶۴ و ۱۲۸ و ... را امتحان می کردیم.
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۵,۰۴۹ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
|
مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۴۱۹ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
مرتبه شبه کد | rad.bahar | ۱ | ۲,۳۷۶ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۳,۲۹۷ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
مرتبه زمانی | Sanazzz | ۱۷ | ۲۱,۸۵۳ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت | اsepid8994 | ۰ | ۱,۸۲۰ |
۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ آخرین ارسال: اsepid8994 |
|
مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۸۶۰ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
مرتبه مانی | Sanazzz | ۳ | ۳,۷۷۶ |
۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz |
|
یافتن دو عدد پیچیدگی زمانی O(n) | porseshgar | ۲ | ۳,۹۸۲ |
۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ آخرین ارسال: porseshgar |
|
مرتبه زمانی | Sanazzz | ۰ | ۲,۰۶۸ |
۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ آخرین ارسال: Sanazzz |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close