(۱۴ اسفند ۱۳۹۰ ۰۵:۵۸ ب.ظ)abcd1234 نوشته شده توسط: کسی میتونه سوال ۵۱ رو توضیح بده؟
سلام به همه دوستان خوب هم رشته ای،
جواب سوال ۵۱ از رابطه بازگشتی قابل محاسبه ست
قبول کنید میشه حدس زد T(n)=n+2*T(n/2) l
اگه قبول نکنید مجبورید این متن طولانی رو بخونید
_____
صورت سوال: ساختار داده شامل مجموعه های Si است که هرکدام صفر یا l 2^n عضو دارند...
فرض کنید چهار تا S داریم با این ترتیب تعداد عناصر [۰][۰][۰][۰]
یکی یکی اضافه کردن هشت عنصر را بررسی می کنیم
[۱][۰][۰][۰]
[۰][۲][۰][۰]
[۱][۲][۰][۰]
[۰][۰][۴][۰]
[۱][۰][۴][۰]
[۰][۲][۴][۰]
[۱][۲][۴][۰]
[۰][۰][۰][۸]
سریعا متوجه میشویم:
چون هر مجموعه صفر یا ۲n^ عضو دارد هنگامی که k عضو در ساختار داده هست، اگر k را با مجموع توان های دو بنویسم، هر کدام از آن اعداد تعداد یکی از S هاست (مثلا ۱۰۰=۶۴+۳۲+۴، پس هنگامی که صد عنصر داریم سه تا از S ها تعداد ۴ و ۳۲ و ۶۴ وبقیه صفر دارند) (و بدیهی است این یک تناظر با باینری نوشتن عدد دارد ۱۰۰D=1100100B)
اگه بیشتر تو این هشت مرحله دقت کنیم متوجه میشیم:
S1 همیشه یا خالی ست یا ۲^۱ عنصر دارد، اما S2 یا خالی ست یا ۲^۲ عضو دارد و S3 2^3 (باز هم تناظر با باینری نوشتن عدد)
اما چطور میفهمیم nlogn:
توضیح میدم چطوری T(n)=n+2*T(n/2) l
فرض کنید n یک عدد توان دو هست، برای نوشتن n عنصر در ساختار ابتدا با صرف مقداری هزینه n/2 عنصر در ساختار میریزیم که پر و خالی بودن مجموعه های S به این صورت در میان: ۰۰۰///۱۰۰۰۰ (توضیح دادم تناظر با باینری نوشتن)
حالا می خواهیم n/2 عنصر دیگه رو اضافه کنیم، همونقدر هزینه میبره که قبلا برد، اما آخرین عنصرش به اندازه n هزینه بیشتر میبره (چون صورت سوال گفته هزینه انتقال برابر مجموع تعداد عناصر است) و این همون T(n)=n+2*T(n/2) l هست
مجبورید قبول کنید که اگه n توان دو هم نبود همین رابطه برقرار بود (اثباتش دور از ذهن نیست)
شاید می پرسید چجوری اینا رو سر جلسه میفهمیدیم جوابش هم اینه که این تحلیلا برای بعد جلسه ست و من سر جلسه نتونستم فکر کنم نزدم