با عرض سلام.الگوریتم ساخت هیپ به این ترتیب هستش که تو یک حلقه For که به تعداد n/2 با تکرار روال Heapify رو اجرا میکنه. مرتبه زمانی روال Heapify برابر است با [tex]T({Logn})[/tex] .پس چرا تو کتابها نوشته شده که میشه اثبات کرد که مرتبه زمانی ساخت هیپ [tex]T({n})[/tex]
(۳۰ دى ۱۳۸۹ ۱۱:۳۸ ق.ظ)sos006 نوشته شده توسط: با عرض سلام.الگوریتم ساخت هیپ به این ترتیب هستش که تو یک حلقه For که به تعداد n/2 با تکرار روال Heapify رو اجرا میکنه. مرتبه زمانی روال Heapify برابر است با [tex]T({Logn})[/tex] .پس چرا تو کتابها نوشته شده که میشه اثبات کرد که مرتبه زمانی ساخت هیپ [tex]T({n})[/tex]اثباتش توی کتاب پوران پژوهش چاپ جدیدش هست در ضمن این مطلب توی همه کتاب های مرجع اومده. به نظرم دیگه دنبال اثبات نباش چون کمتر از ۱ ماه وقت مونده.
یه روش دیگه هست که اول همه عناصر رو میریزید داخل یه درخت (آرایه) بعد hepify رو اجرا میکنید.برای هر پدر heapify رو انجام میدیم و چون تعداد گره های غیر برگ n/2 است در زمان کمتری هیپ ساخته میشود.
روال Heapify به ارتفاع درخت وابسته است که اثبات میشه که [tex]O(lgn)[/tex] هست.(توصیه میکنم که سعی کنید که رابطه‌ی بازگشتیشو بنویسید و بدستش بیارید چونکه چند نکته مهم توی اثباتش وجود داره)
هدف ساختن هیپ است و روال هیپیفای روی گره های مورد نظر یکی یکی بررسی می شود.حالا این گره‌ها چه حالتهایی دارند؟ممکنه گره‌ی جدید توی همون برگی که اضافه میشه بمونه ممکن هم هست بیاد بالا تا ریشه.پس از نظر مرتبه‌ی زمانی نمی تونیم بگیم همشون محکومند که [tex]O(lgn)[/tex] بشوند.
پس در ابتدا باید تعداد گره‌ها را در هر ارتفاعی از Heap را بر حسب اختلاف ارتفاعشون از برگها بدست بیاریم و این تعداد را در مرتبه زمانی همون سطح(بخاطر Heapify)ضرب کنیم.
تعداد حداکثر گره در ارتفاع h در یک Heap برابر است با: [tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil[/tex]
{اگر بحثی روی این رابطه دارید توی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
که پرسیده بودید بیان کنید}
پس با توجه به توضیحاتی که عنوان شد داریم:
[tex]\sum_{h=0}^{\left \lfloor \lg{n} \right \rfloor}\left \lceil \frac{n}{2^{h 1}} \right \rceil\times O(h) =O(n\sum_{h=0}^{\left \lfloor \lg{n} \right \rfloor}\left \lceil \frac{h}{2^{h 1}} \right \rceil)[/tex]
جواب سیگما محدوده(کوچکتر از ۲ خواهد بود).اثباتش اهمیتی نداره و این مورد را همینطوری قبول کنید! در نتیجه مرتبه برابر [tex]O(n)[/tex] میشود.
(۳۰ دى ۱۳۸۹ ۰۱:۴۲ ب.ظ)afagh1389 نوشته شده توسط: یه روش دیگه هست که اول همه عناصر رو میریزید داخل یه درخت (آرایه) بعد hepify رو اجرا میکنید.برای هر پدر heapify رو انجام میدیم و چون تعداد گره های غیر برگ n/2 است در زمان کمتری هیپ ساخته میشود.
روش مورد بحث همین روش است و ایشون هم مرتبه‌ی زمانی همین روش را پرسیدند!
(۳۰ دى ۱۳۸۹ ۰۲:۴۹ ب.ظ)حامد نوشته شده توسط:(30 دى ۱۳۸۹ ۰۱:۴۲ ب.ظ)afagh1389 نوشته شده توسط: یه روش دیگه هست که اول همه عناصر رو میریزید داخل یه درخت (آرایه) بعد hepify رو اجرا میکنید.برای هر پدر heapify رو انجام میدیم و چون تعداد گره های غیر برگ n/2 است در زمان کمتری هیپ ساخته میشود.
روش مورد بحث همین روش است و ایشون هم مرتبه‌ی زمانی همین روش را پرسیدند!
بله ایشون گفتن که " الگوریتم ساخت هیپ به این ترتیب هستش که تو یک حلقه For که به تعداد n/2 با تکرار روال Heapify رو اجرا میکنه " منم گفتم دلیل این که O(n شده اینه که از روش دیگری استفاده کردن و روش رو توضیح دادم.
(۳۰ دى ۱۳۸۹ ۰۳:۳۳ ب.ظ)afagh1389 نوشته شده توسط: بله ایشون گفتن که " الگوریتم ساخت هیپ به این ترتیب هستش که تو یک حلقه For که به تعداد n/2 با تکرار روال Heapify رو اجرا میکنه " منم گفتم دلیل این که O(n شده اینه که از روش دیگری استفاده کردن و روش رو توضیح دادم.
روشی که شما توضیح دادید دقیقا همون روشی هست که ایشون گفتند.و [tex]\frac{n}2[/tex] تکرار ایشون هم برای گره های پدر می باشد.
دلیل اینکه روی این موضوع تاکید دارم اینه که بقیه‌ی الگوریتم هایی که برای این کار وجود داره مرتبشون فرق میکنه.(از جمله روشی که یکی یکی گره‌ها رو اضافه میکنیم نه آرایه ای)
آره از مرتبه n هست .
اثباتش هم صفحه ۱۳۶ CLRS هست.
اینکه خودمون اشتباها فک میکنیم در زمان nlogn هست به خاطر این هست که ارتفاع تمام گره‌ها رو logn میگیریم.
در صورتی که همونطور که حامد در بالا گفته تمام گره‌ها این ارتفاع رو ندارن.
یعنی فقط گره های سطح آخر ارتفاعشون logn هست و بقیه همه کمتر از n هستند.
من میگم درج همون ساخت هست که زمانش هم n هست.
اینو هم یک نگاه بندازید:
[attachment=377]
نه
درج هر گره زمان (O(h میبره که h هم حداکثر میتونه logn باشه و در سطحهای اولی مطمئنا زمان درج که همون ارتفاع هست logn نمیشه و میشه ارتفاع در همون سطحی که میخاد گره اضافه بشه.
برای حذف هم به نظرم زمان حذف اولین بار logn هست و دفعات بعد همونطور که پیش میریم و حذف رو ادامه بدیم مرتبه حذف کم میشه چون ارتفاع داره کمتر میشه و در واقع برابر ارتفاع جدید هست.
فک کنم بد توضیح دادم!!
نه عالی بود
در این فاصله من کمی فکر کردم و پاسخ دقیق رو پیدا کردم
ادغام دو هیپ n هست
ساخت هیپ هم n هست
درج در هیپ log(n هست
حذف هم log(n هست
نکته اینجاست که در ادغام ما محل درج عنصر جدید رو همیشه داریم و یکی یکی جلو می بریمش، درصورتیکه در مورد درج عنصر جدید، محل درج مشخص نیست و بنابراین باید با مرتبه لگاریتمی پیداش کنیم