(۱۴ اسفند ۱۳۹۰ ۱۲:۲۸ ب.ظ)anyone نوشته شده توسط: به نظرم ابن سوال مربوط به حذف و درج داده در ساختمان داده های جدا از هم باشه.(فصل۲۱ کورمن)
درج یک داده از مرتبه logn ، برای درج کل عناصر از مرتبه nlogn خواهد بود، فکر نمی کنم بشه این کار رو با هزینه کمتری انجام داد.
آخه با توضیحاتی که تو صورت سوال داده برای درج عنصر nام همه n-1 عنصر قبلی باید مجددا درج بشن که هزینه اش برای n عنصر بیشتر از nlgn میشه، برای هر عنصر n و برای n عنصر میشه n^2
به نظر من هم توضیحات خیلی واضع نبودند ولی به نظرم این کار با این ساختمان داده قابل انجامه پس این هزینه منطقیه اما در مورد هزینه کمتر نظری ندارم
کسی میتونه سوال ۵۱ رو توضیح بده؟
(۱۴ اسفند ۱۳۹۰ ۰۵:۵۸ ب.ظ)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 توان دو هم نبود همین رابطه برقرار بود (اثباتش دور از ذهن نیست)
شاید می پرسید چجوری اینا رو سر جلسه میفهمیدیم جوابش هم اینه که این تحلیلا برای بعد جلسه ست و من سر جلسه نتونستم فکر کنم نزدم
(۱۵ اسفند ۱۳۹۰ ۱۲:۱۸ ق.ظ)mohammad_13690 نوشته شده توسط:شما درست می فرمائید(14 اسفند ۱۳۹۰ ۰۵:۵۸ ب.ظ)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 توان دو هم نبود همین رابطه برقرار بود (اثباتش دور از ذهن نیست)
شاید می پرسید چجوری اینا رو سر جلسه میفهمیدیم جوابش هم اینه که این تحلیلا برای بعد جلسه ست و من سر جلسه نتونستم فکر کنم نزدم
اما اگر با لیست پیوندی یا لیست های زنجیری و در نظر گرفتن "..پس از انتقال مجموعه های s0 , s1,.., sn خالی شوند(طبق سوال) "
می توان آن را با o(n پیاده سازی کرد
مگه تفاوتی می کنه با لیست پیوندی باشه یا آرایه؟
طبق توضیح من هم وقتی یک عنصر توی Sk ریخته میشه، S0 تا Sk-1 خالی میشه و من متوجه نشدم چجوری از این ها به O(n رسیدید. میشه بیشتر توضیح بدید
(۱۶ اسفند ۱۳۹۰ ۱۱:۴۸ ب.ظ)mohammad_13690 نوشته شده توسط:اگر در هر مرحله لیست پیوندی را به صورت زنجیر در نظر بگیریم(نه لیست رنجیری ، با لیست زنجیری هم "ترکیب آرایه و لیست های پیوندی " می توان با o(n پیاده سازی کرد ) به جای حذف s0 تا sk-1 می توان زنجیر را شکست و انتقال داد (بدون اضافه شدن هزینه حذف عناصر- تنها با تغییر اتصال ها) در نتیجه هزینه افزودن n عنصر باقی می ماند(16 اسفند ۱۳۹۰ ۱۰:۲۴ ب.ظ)n_alaie نوشته شده توسط:مگه تفاوتی می کنه با لیست پیوندی باشه یا آرایه؟
طبق توضیح من هم وقتی یک عنصر توی Sk ریخته میشه، S0 تا Sk-1 خالی میشه و من متوجه نشدم چجوری از این ها به O(n رسیدید. میشه بیشتر توضیح بدید
(۱۷ اسفند ۱۳۹۰ ۰۷:۱۰ ب.ظ)n_alaie نوشته شده توسط:(16 اسفند ۱۳۹۰ ۱۱:۴۸ ب.ظ)mohammad_13690 نوشته شده توسط:اگر در هر مرحله لیست پیوندی را به صورت زنجیر در نظر بگیریم(نه لیست رنجیری ، با لیست زنجیری هم "ترکیب آرایه و لیست های پیوندی " می توان با o(n پیاده سازی کرد ) به جای حذف s0 تا sk-1 می توان زنجیر را شکست و انتقال داد (بدون اضافه شدن هزینه حذف عناصر- تنها با تغییر اتصال ها) در نتیجه هزینه افزودن n عنصر باقی می ماند(16 اسفند ۱۳۹۰ ۱۰:۲۴ ب.ظ)n_alaie نوشته شده توسط:مگه تفاوتی می کنه با لیست پیوندی باشه یا آرایه؟
طبق توضیح من هم وقتی یک عنصر توی Sk ریخته میشه، S0 تا Sk-1 خالی میشه و من متوجه نشدم چجوری از این ها به O(n رسیدید. میشه بیشتر توضیح بدید
راه حلتون درسته
اما توی صورت سوال داریم:
"...دقت کنید که پس از این انتقال مجموعه های S1 ، S0 تا Si-1 خالی می شوند و هزینه انتقال برابر مجموع تعداد این عناصر است..."
کاش سر جلسه متوجه این قسمت می شدید