(۱۷ آذر ۱۳۹۳ ۱۱:۳۱ ق.ظ)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] میشه