فکر کنم کلیدتون اشتباست ، برای من جوابو نوشته logn

کلا مرتبه حذف عنصر از هیپ میشه logn

کافیه گره حذف بشه و یک بار Max-Heapify فراخوانی بشه. که اینم میشه log n

نه اتفاقا من با nlogn کاملا موافقم.
ببینید منطقش اینه: چون نمیتونیم از وسط هیپ گرهی رو حذف کنیم باید انقدر از بالا (ریشه) حذف کنیم تا برسیم به اون گره دلخواه دیگه. بعد میتونیم اون گره دلخواه رو حذف کنیم. پس در بدترین حالت میشه از مزتبه nlogn
چون خود حذف که logn میشه، حالا در بدترین حالت برای حذف عنصر i ام باید n بار حذف کنیم و مرتب کنیم که میشه nlogn
من نمیدونم پس چرا مقسمی گفته n!!!

اینجا رو ببینین

(۲۳ بهمن ۱۳۹۲ ۱۲:۰۸ ب.ظ)tayebe68 نوشته شده توسط:  اینجا رو ببینین

کجا رو دقیقا؟؟
واسه من چیزی نیومده!
الان شما با این منطقی که مدرسان آورده مخالفین؟؟با nlogn ؟؟

(۲۳ بهمن ۱۳۹۲ ۱۲:۳۴ ب.ظ)mhd3 نوشته شده توسط:  

(23 بهمن ۱۳۹۲ ۱۲:۰۸ ب.ظ)tayebe68 نوشته شده توسط:  اینجا رو ببینین

کجا رو دقیقا؟؟
واسه من چیزی نیومده!
الان شما با این منطقی که مدرسان آورده مخالفین؟؟با nlogn ؟؟

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(۲۳ بهمن ۱۳۹۲ ۱۲:۴۳ ب.ظ)tayebe68 نوشته شده توسط:  
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

مرسی. خیلی ممنونم.
فقط یه سوال کوچولو. بنطرتون چرا مقسمی گفته حذف یک عنصر دلخواه میشه از مرتبه n؟؟
وقتی شروع کرده BST رو درس بده اولش گفته که حذف یک عنصر دلخواه از درخت هیپ با n عنصر برابر n است. این زمان ارجحیتی نسبت به زمان مورد نیاز برای حذف یک عنصر دلخواه از لیست نامرتب ندارد.
---------------------------
بعد یه سوال دیگه. تو این عکس:




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

(۲۳ بهمن ۱۳۹۲ ۰۱:۲۰ ب.ظ)mhd3 نوشته شده توسط:  بنطرتون چرا مقسمی گفته حذف یک عنصر دلخواه میشه از مرتبه n؟؟
وقتی شروع کرده BST رو درس بده اولش گفته که حذف یک عنصر دلخواه از درخت هیپ با n عنصر برابر n است. این زمان ارجحیتی نسبت به زمان مورد نیاز برای حذف یک عنصر دلخواه از لیست نامرتب ندارد.

متاسفانه اشتباه گفته

(۲۳ بهمن ۱۳۹۲ ۰۱:۲۰ ب.ظ)mhd3 نوشته شده توسط:  بعد یه سوال دیگه. تو این عکس:
مدرسان گفته حذف و کاهش از مرتبه n
اما درج از مرتبه logn
بخاطر همین گزینه ۲ رو انتخاب کرده. پس اینم اشتباهه دیگه. کاهش از چه مرتبه ایه؟؟
اصلا نمیشه به این مدرسان اعتماد کرد... تکلیفش با خودش مشخص نیست!!

تو این سوال هم هر سه عمل در زمان logn انجام میشن
کلید سنجش هم گزینه چهاره

اشتباهشون اینه که فکر کردن اول باید بگردن عنصر رو پیدا کنن، بعد حذفش کنن، در حالی که تو صورت سوال خواسته نشده یک عنصر خاص رو حذف کنیم ، گفته یه عنصر دلخواه

(۲۳ بهمن ۱۳۹۲ ۰۱:۲۰ ب.ظ)mhd3 نوشته شده توسط:  مدرسان گفته حذف و کاهش از مرتبه n
اما درج از مرتبه logn
بخاطر همین گزینه ۲ رو انتخاب کرده. پس اینم اشتباهه دیگه. کاهش از چه مرتبه ایه؟؟
اصلا نمیشه به این مدرسان اعتماد کرد... تکلیفش با خودش مشخص نیست!!

به طور کلی در هرم :
۱- MAX-Heapify با مرتبه log n
۲- ساخت هرم : n
۳- ساخت هرم از طریق درج : n log n
۴- Heap Sort : مرتبه n log n
۵- درج ، حذف یک کلید ، حذف max و افزایش و کاهش کلید با مرتبه log n
--------------------------------
این لینک هم ببینید بد نیست :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

خیلی ممنونم از هردوتون