با عرض سلام
تحلیل من از سوال های مثل سوال زیر اینه که
۱) هربار آرایه به دو نیمه تقسیم می شه و دوباره تابع مورد نظر فراخوانی می شه
۲) در هر مرحله یک مقایسه بین دو عنصر m1 و m2 انجام می شه
یعنی کلا log (n) مرتبه تابع فراخوانی می شه و در هر بار یک مقایسه انجام می شه یعنی log (n) مرتبه مقایسه
چرا جواب می شه گزینه ی ۱ ؟
سلام.
چون این سوالا رو میپیچونن نمیشه چشمی گفت چی میشه، ممکنه یه متغیری یه جایی تغییر کنه و مرتبه عوض بشه.
(ببخشید اگه از اول بدیهیات رو مینویسم چون دارم همزمان حل میکنم مینویسم)
خب الان تابع ظاهرا داره مثل جستجوی دودویی آرایه رو نصف میکنه.
i اندیس ابتدای آرایه و j اندیس انتهای آرایه ی A هست. و ورودی تابع آرایه ی A و اندیس ابتدا و انتهاش هست.
اولش n=j-i+1 که یعنی n طول آرایه (تعداد اعضای آرایه) رو نگه میداره. خب اولش n=طول آرایه هست. اگه ۱ بود یعنی کلا آرایه یک عضو داشت [tex]A[i][/tex] رو برمیگردونه که همون عضو هست در غیر این صورت همین تابع رو برای نیمه ی اول آرایه فراخوانی میکنه و نتیجه ش رو توی m1 میریزه. و همین تابع رو برای نیمه ی دوم فراخوانی میکنه و توی m2 می ریزه. بعد یه مقایسه انجام میده و هر کدوم از اینا که بزرگتر بود رو بر میگردونه.
حالا باید ببینیم چند بار مقایسه انجام میشه. یعنی خط ۶.
این جا چون مرتبه رو نگفته و دقیق با ثوابت گفته پس میشه عددگذاری هم کرد.
برای آرایه ی ۱ عنصری دیدیم که مقایسه انجام نمیشه یعنی ۰ بار که اینطوری گزینه ی ۳ حذف میشه.
برای آرایه ی ۲ عنصری توی فراخوانی نیمه ی اول خونه ی اندیس ۱ میره توی m1 و توی فراخوانی نیمه ی دوم خونه ی اندیس ۲ میره توی M2 و حالا یک مقایسه براش کافی هست. یعنی یک بار مقایسه. اینطوری گزینه ی ۲ حذف میشه.
برای آرایه ی ۳ عنصری توی فراخوانی نیمه ی اول خونه ی اندیس ۱ میره توی m1 و توی فراخوانی نیمه ی دوم خونه ی اندیس ۲ و ۳ به عنوان ورودی تابع هستن. پس لازمه یه بار دیگه م صدا زده بشه و بین این دو تا اندیس ۲ و ۳ بزرگترینش برگردونده بشه و بعد با خونه ی ۱ مقایسه بشه. یعنی ۲ تا مقایسه. پس گزینه ی ۴ هم رد میشه.
اینطوری میبینیم که اگه طول آرایه فرد باشه از اندیس ۱ تا اندیس وسط منهای ۱ یه بار به عنوان ورودی تابع میره و از بعدش تا آخر به عنوان یه ورودی دیگه. اگه فرض کنیم زوج باشه n اونوقت [tex]\frac{N}{2}[/tex] عنصر یه بار صدا زده میشن و[tex]\frac{N}{2}[/tex] عنصر دیگه به عنوان ورودی تابع. که هر کدوم [tex]\frac{N}{2}-۱[/tex] مقایسه دارن و در نهایت ماکسیمم هر کدوم ازشون با هم یه بار مقایسه میشه و کلا تعداد مقایسات میشه [tex]2\times(\frac{n}{2}-1)+1=n-1[/tex]
سلام دوست عزیز ، خیلی لطف کردید. بسیار سپاسگزارم