سلام بچها خسته ام نباشین
سوال ۳۷ فصل اول قدسی فرموده که: P مساله ای است که پیچیدگی آن در بدترین حالت( bigomega(n^2 و نیز(little o (n^3 الگوریتم A,
P را حل میکند.کدامیک از گزینه های زیر می تواند پیچیدگی A باشد؟
بعد جوابش شده tetaye n^2
توی راه حل تشریحیش گفته درجه رشد مورد نظر باید کمتر از n^3 و بیشتر یا مساوی n^2 باشد...
حالا سوالم اینه که مگه ما نمیگیم bigomega میشه کوچیکتر یا مساوی؟؟و little o میشه فقط بزرگتر؟؟؟پس چرا اینجا اینجور شده؟؟؟
پیش پیش ممنون از جواباتون
نبود؟؟؟
سلام ببین صورت سوال گفته پیچیدگیش در بدترین حالت [tex]Ω(n^2)[/tex] و [tex]o(n^3)[/tex] هستش خب؟
حالا گزینه ها رو بررسی میکنیم:
گزینه اول[tex][tex]\leftarrow[/tex][/tex][tex]O(n^4)[/tex][tex][tex]\leftarrow[/tex][/tex]اگه پیچیدگی زمانی [tex]A[/tex] این باشه پس [tex]A[/tex] میتونه مثلا زمان اجرایی مثل [tex]cn^4[/tex] رو داشته باشه که این فرض مساله رو نقض میکنه چون توی صورت سوال گفته [tex]o(n^3)[/tex] یعنی زمان اجرایی کمتر از [tex]n^3[/tex] باید داشته باشه
گزینه دوم[tex][tex]\leftarrow[/tex][/tex][tex]o(n^2)[/tex][tex][tex]\leftarrow[/tex][/tex] خب اینجا هم شرط مساله رو نقض کردیم چون گفتیم که زمان اجرای [tex]A[/tex] حداقل [tex]Ω(n^2)[/tex] هست ولی [tex]o(n)[/tex] یعنی مرتبه زمانی [tex]A[/tex] حتما باید از [tex]n[/tex] کمتر باشه که این گزینه هم با فرض مساله تناقض داره
گزینه سوم[tex][tex]\leftarrow[/tex][/tex][tex]\theta(n^3)[/tex][tex][tex]\leftarrow[/tex][/tex] خب میدونیم [tex]\theta[/tex] یعنی هم عضو [tex]O[/tex] و هم عضو [tex]Ω[/tex].پس تو این گزینه داریم:
[tex]\theta(n^3)\rightarrow O(n^3)\: and\: Ω(n^3)[/tex]
که قسمت اول بازم فرض مساله رو نقض میکنه چون تو فرض مساله گفتیم که زمان اجرا حتما باید از [tex]n^3[/tex] کوچکتر باشه
گزینه چهارم[tex][tex]\leftarrow[/tex][/tex][tex]\theta(n^2)[/tex][tex][tex]\leftarrow[/tex][/tex] خب برای این مرتبه زمانی هم داریم:
[tex]\theta(n^2)\rightarrow O(n^2)\: and\: Ω(n^2)[/tex]
که میبینی تمام شرایط گفته شده مساله رو هم حفظ کرده و هیچ تناقضی با اونا نداره
پس جواب [tex]\theta(n^2)[/tex] میشه
(۱۷ آذر ۱۳۹۳ ۱۱:۳۱ ق.ظ)miladcr7 نوشته شده توسط: سلام ببین صورت سوال گفته پیچیدگیش در بدترین حالت [tex]Ω(n^2)[/tex] و [tex]o(n^3)[/tex] هستش خب؟اقا متشکر
حالا گزینه ها رو بررسی میکنیم:
گزینه اول[tex][tex]\leftarrow[/tex][/tex][tex]O(n^4)[/tex][tex][tex]\leftarrow[/tex][/tex]اگه پیچیدگی زمانی [tex]A[/tex] این باشه پس [tex]A[/tex] میتونه مثلا زمان اجرایی مثل [tex]cn^4[/tex] رو داشته باشه که این فرض مساله رو نقض میکنه چون توی صورت سوال گفته [tex]o(n^3)[/tex] یعنی زمان اجرایی کمتر از [tex]n^3[/tex] باید داشته باشه
گزینه دوم[tex][tex]\leftarrow[/tex][/tex][tex]o(n^2)[/tex][tex][tex]\leftarrow[/tex][/tex] خب اینجا هم شرط مساله رو نقض کردیم چون گفتیم که زمان اجرای [tex]A[/tex] حداقل [tex]Ω(n^2)[/tex] هست ولی [tex]o(n)[/tex] یعنی مرتبه زمانی [tex]A[/tex] حتما باید از [tex]n[/tex] کمتر باشه که این گزینه هم با فرض مساله تناقض داره
گزینه سوم[tex][tex]\leftarrow[/tex][/tex][tex]\theta(n^3)[/tex][tex][tex]\leftarrow[/tex][/tex] خب میدونیم [tex]\theta[/tex] یعنی هم عضو [tex]O[/tex] و هم عضو [tex]Ω[/tex].پس تو این گزینه داریم:
[tex]\theta(n^3)\rightarrow O(n^3)\: and\: Ω(n^3)[/tex]
که قسمت اول بازم فرض مساله رو نقض میکنه چون تو فرض مساله گفتیم که زمان اجرا حتما باید از [tex]n^3[/tex] کوچکتر باشه
گزینه چهارم[tex][tex]\leftarrow[/tex][/tex][tex]\theta(n^2)[/tex][tex][tex]\leftarrow[/tex][/tex] خب برای این مرتبه زمانی هم داریم:
[tex]\theta(n^2)\rightarrow O(n^2)\: and\: Ω(n^2)[/tex]
که میبینی تمام شرایط گفته شده مساله رو هم حفظ کرده و هیچ تناقضی با اونا نداره
پس جواب [tex]\theta(n^2)[/tex] میشه