(۰۱ اردیبهشت ۱۳۹۵ ۰۹:۲۵ ق.ظ)dokhtare payiz نوشته شده توسط:  میشه بگین چرا گزینه ۳ درسته؟

سلام
دو فرض رو در نظر بگیرین یکی A زوج باشه یکی فرد
وقتی A زوج باشه از قسمت سوم ضابطه استفاده میکنه و هربار به طور بازگشتی A نصف میشه تا به شرط بن بست برسیم
[tex]A:even->\: 1 h(\frac{A}{2})=1 1 h(\frac{A}{4})=1 1 1 h(\frac{A}{8})=...\: =\log A\: h(0)=\log A[/tex]

فرض دوم A فرد باشه پس از قسمت دوم میریم اول یکی از A کم کرده تو روابط اینطوری حتما یکی در میان A زوج شده حالا که زوجه از رابطه اول استفاده میشه تا به شرط بن بست برسیم عمل تقسیم سریع تر از کم شدن باعث رسیدن به شرط بن بست میشه

سلام

اگه توجه بفرمایید A زمانی که زوج باشه نصف میشه در بدترین حالت یکی در میون زوج میشه و طبق بازگشت نصف میشه بنابراین علیرغم کاهش یک واحدی در برابر نصف شدن ها ناچیز هست بنابراین انگار اصلا اون کاهش یک واحدی نیست که مرتبه میشه logA.
سعی کردم خودمانی بگم حل ریاضیش فکر کنم تو همه کتابا باشه.

ممنون, توجیه شدم.