تالار گفتمان مانشت

چرا لگاریتم ؟

در این مسئله هر بار اول به روش دودویی(که از مرتبه log n هست) تعداد تکرار عنصر وسط آرایه شمارش میشه و هر بار آرایه نصف میشه و برای هر نیمه همین کار تکرار میشه(که این عمل تقسیم هم از مرتبه log n هست) و به نظرم در آخرین مرحله فقط تعداد عناصر آرایه باقیمانده را میشمریم. زمان ادغام هم نداریم چون قبل از تقسیم کردن اعداد شمارش شدند.
به نظر من جواب رابطه بازگشتی گزینه 3 است

اصلا این چطور سوالی هستش؟
اولش گفته تعداد تکرار هر یک از اعداد رو محاسبه کنیم.
بعدش گفته با استفاده از جستجوی دودویی ابتدا و انتهای تکرار عدد 8 رو پیدا می کنیم!!!

ما نفهمیدیم میخواد تعداد تکرار هر یک از اعداد رو جستجو کنه یا عدد 8 رو؟

---

(23 بهمن 1390 05:44 ب.ظ)fatima1537 نوشته شده توسط: [ -> ]در این مسئله هر بار اول به روش دودویی(که از مرتبه log n هست) تعداد تکرار عنصر وسط آرایه شمارش میشه و هر بار آرایه نصف میشه و برای هر نیمه همین کار تکرار میشه(که این عمل تقسیم هم از مرتبه log n هست) و به نظرم در آخرین مرحله فقط تعداد عناصر آرایه باقیمانده را میشمریم. زمان ادغام هم نداریم چون قبل از تقسیم کردن اعداد شمارش شدند.
به نظر من جواب رابطه بازگشتی گزینه ۳ است

گزینه دوم شده

(23 بهمن 1390 05:45 ب.ظ)پشتکار نوشته شده توسط: [ -> ]گزینه دوم شده

من ید طولایی تو منفی زدن دارم!

---

شاید به این خاطر گزینه ۲ میشه که هربار فقط عناصر وسط آرایه با مرتبه lognشمارش میشن این کار logn مرتبه تکرار میشه