کامپیوتری در واحد زمان مساله ای به اندازه‌ی ۱۶ را که الگوریتم آن از مرتبه زمانی [tex]n2^{n}[/tex] است حل می کند.اگر سرعت کامپیوتر ۱۳۱۰۷۲ برابر گردد این کامپیوتر همان مساله را با چه اندازه ای در واحد زمان حل خواهد کرد؟
۱۶+۱۷+log17
۱۶*۱۷*log17
۳۲
۱۶+log131072
۱۳۱۰۷۲ همون [tex]2^{17}[/tex] هست.
توی پوران یه فرمول ضمن درس گفته ولی من با اون به جواب نرسیدم.حل خودشو متوجه نشدم.گزینه ۳ درسته(۳۲)
درواقع صورت مسئله گفته که کامپیوتری در یک ثانیه مسئله ای به اندازه ۱۶ را، با الگوریتمی که مرتبه اجرای ان ۱۶^۲*۱۶ هست رو حل میکنه. حالا سرعت اجرا ۱۷^۲ برابر شده . من چند روش رو رفتم ولی هیچ کدوم از گزینه‌ها جواب نبود
میشه جوابش رو ضمیمه کنید؟
یک واحد زمانی ما چیزی به این صورت:
[tex]T = 16*2^1^6[/tex]
از طرف دیگه می دونیم که:
[tex]2^1^7 = 131072[/tex]
ضمنا در فرمول های مربوط به مرتبه زمانی یک ثابتی هم وجود داره (مثل C) که مربوط به سایر عوامل تاثیر گذار روی زمان اجرای الگوریتم میشه (مثل سرعت سخت افزار). یعنی می تونیم بگیم که مرتبه اجرایی این الگوریتم بصورت زیر:
[tex]T=c*n*2^n[/tex]
حالا مقدار c در کامپیوتر جدید [tex]2^1^7[/tex] برابر کمتر. یعنی می تونیم بگیم که در کامپیوتر جدید:
[tex]T=1/2^1^7*n*2^n[/tex]
که اگر مقدار یک مرتبه زمانی رو قرار بدیم خواهیم داشت:
[tex]16*2^1^6=1/2^1^7*n*2^n[/tex]
[tex]32*2^3^2 = n*2^n[/tex]
که نتیجه میده:
[tex]n=32[/tex]
امیدوارم درست فهمیده باشم.
(۱۸ دى ۱۳۹۰ ۰۶:۲۷ ب.ظ)shervinrs نوشته شده توسط: یک واحد زمانی ما چیزی به این صورت:درسته من فکر میکردم چون گفته یک واحد زمانی پس به جای n، عدد ۱ رو جایگذاری میکنیم.
[tex]T = 16*2^1^6[/tex]