خسته نباشید
میخواستم ببینم چجوری زمان اجرای ساخت heap برابر [tex]O(n)[/tex] میشه محاسبات کتاب پوران رو متوجه نمیشم
و طبق الگوریتم کتاب چرا [tex]n.\lg(n)[/tex] نمیشه؟
ا الان جزوه رو دیدم اونم [tex]n.\lg(n)[/tex] نوشته.حالا کدوم زمان درسته؟
سلام
nlogn مربوط به nبار استفاده از الگوریتم heapify هست که n عضو را به هیپ add میکنه که هرکدوم logn مصرف میکنه.
ولی روش دیگه ای هست که در جا کار رو انجام میده و از عنصر n/2 به قبل رو بالامیاد و جای عنصر با فرزندان رو بررسی میکنه که مرتبه (n) هست
جرییاتش یادم نیست ولی سعی میکنم براتون بذارم
مرسی ممنون میشم اینکارو انجام بدید
تو جلسه چهارم استاد یوسفی کامل توضیح داد که چرا میشه n
یه الگوریتم هست تو تستها که اون در اصل heapify ساخت heapکه بهترین زمان n میشه
(۱۴ مرداد ۱۳۹۳ ۰۴:۵۶ ب.ظ)miladcr7 نوشته شده توسط: خسته نباشید
میخواستم ببینم چجوری زمان اجرای ساخت heap برابر [tex]O(n)[/tex] میشه محاسبات کتاب پوران رو متوجه نمیشم
و طبق الگوریتم کتاب چرا [tex]n.\lg(n)[/tex] نمیشه؟
ا الان جزوه رو دیدم اونم [tex]n.\lg(n)[/tex] نوشته.حالا کدوم زمان درسته؟
دو بحث اینجا هست یک بار ممکن بپرسن مرتب سازی به روش heap چطوری انجام میشه اون وقت جواب قطعا nlogn
اما یک وقت می پرسن خود ساخت heap چه مرتبه زمانی داره که دو راه براش وجود داره یک راه پیش راه افتاده اینکه دونه دونه اعداد را وارد درخت هیپ کنیم اون وقت مرتبه اش میشه nlogn
راه دوم که دوستان اشاره کردن اینکه ارایه ورودی را به عنوان یک درخت پیش فرض در نظر بگیرم و از ریشه تا نصف گره ها ( در واقع میشه تمام گره هایی که یک گره زیر خودشون دارند ) الگوریم Max-Heapify را اجرا کنیم اثبات میشه که مرتبه این الگورتیم میشه n
این دو تا لینک فکر کنم بهت کمک کنه
courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مرسی بچه ها خیلی لطف کردین