(۱۴ اسفند ۱۳۹۰ ۰۶:۲۴ ب.ظ)abcd1234 نوشته شده توسط: سوالای ۱۱۰ و ۱۱۳ رو کسی میتونه توضیح بده؟
سوال ۱۱۰
سوال راحتی بود که، چون توی گزینه ها [logn-1] و [logn+1] و از این چیزا نداشت و کافی بود ببینی از چه مرتبه ایه
هر بار مساله رو نصف میکنه و بدون هزینه ترکیب میکنه (T(n)=2*T(n/2
توی این جور مسائل درنظر بگیرید اگه اندازه آرایه دو برابر بشه، هزینه ۱ مقایسه بیشتر میشه و این خاصیت شگفت انگیز لگاریتمه
______________________
سوال ۱۱۳
سوال قشنگیه، از نظر ذهنی میتونستید تشخیص بدید همون خاصیت لگاریتم صادقه؛ و با یک مقایسه نصف آرایه حذف میشه
اما توضیح دقیق تر یک الگوریتم پیشنهادی:
می دونیم: برای پیدا کردن کوچکترین عنصر در یک آرایه حلقوی مرتب، باید جایی که آرایه ناگهان خیلی بزرگ میشه رو پیدا کنیم
مثال صورت سوال: [۵۰,۴۰,۳۰,۲۰,۱۰,۸۰,۷۰,۶۰]
عنصر اول رو تو متغیر a میریزیم (این کار هزینه نداره)
عنصر وسط رو چک میکنیم؛ اینجا ۲۰
آرایه از ۵۰ به ۲۰ رسیده و جهش ناگهانی رو نداشته پس حالا نصف اول آرایه رو کنار میذاریم
دقت داشته باشید بعد از این بزرگ شدن ناگهانی، بزرگترین عضو آرایه هست و تمام عناصر بعد از اون جهش هم از همه ی عناصر قبل از جهش بزرگترند، پس اگه اون جهش قبل از عنصر وسط بود، حالا این عنصر وسط بزرگ تر از عنصر اول بود
به محض این که متوجه شدید با هزینه ۱ میشه نصف آرایه رو حذف کرد بزنید logn