سلام
مقسمی تو درسنامش گفته مرتبه حذف یک عنصر دلخواه ار درخت هیپ با n عنصر برابر (O( n
اما تست 42 آی تی 90 گفته یک maxheap با n عنصر را که در آرایه [ A [1..n
قرار دارد در نظر بگیرید، مرتبه زمانی الگوریتم حذف عنصر i ام از این ماکس هیپ به گونه ای که ساختار ماکس هیپ را حفظ کند چیست؟
جوابشم گفته nlogn
الان کدوم درسته؟؟ حذف عنصر i ام با حذف یک عنصر دلخواه فرق داره مگه؟؟
فکر کنم کلیدتون اشتباست ، برای من جوابو نوشته logn
کلا مرتبه حذف عنصر از هیپ میشه logn
کافیه گره حذف بشه و یک بار Max-Heapify فراخوانی بشه. که اینم میشه log n
نه اتفاقا من با nlogn کاملا موافقم.
ببینید منطقش اینه: چون نمیتونیم از وسط هیپ گرهی رو حذف کنیم باید انقدر از بالا (ریشه) حذف کنیم تا برسیم به اون گره دلخواه دیگه. بعد میتونیم اون گره دلخواه رو حذف کنیم. پس در بدترین حالت میشه از مزتبه nlogn
چون خود حذف که logn میشه، حالا در بدترین حالت برای حذف عنصر i ام باید n بار حذف کنیم و مرتب کنیم که میشه nlogn
من نمیدونم پس چرا مقسمی گفته n!!!
(23 بهمن 1392 12:08 ب.ظ)tayebe68 نوشته شده توسط: [ -> ]اینجا رو ببینین
کجا رو دقیقا؟؟
واسه من چیزی نیومده!
الان شما با این منطقی که مدرسان آورده مخالفین؟؟با nlogn ؟؟
(23 بهمن 1392 12:43 ب.ظ)tayebe68 نوشته شده توسط: [ -> ]
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مرسی. خیلی ممنونم.
فقط یه سوال کوچولو. بنطرتون چرا مقسمی گفته حذف یک عنصر دلخواه میشه از مرتبه n؟؟
وقتی شروع کرده BST رو درس بده اولش گفته که حذف یک عنصر دلخواه از درخت هیپ با n عنصر برابر n است. این زمان ارجحیتی نسبت به زمان مورد نیاز برای حذف یک عنصر دلخواه از لیست نامرتب ندارد.
---------------------------
بعد یه سوال دیگه. تو این عکس:
[
attachment=15376]
مدرسان گفته حذف و کاهش از مرتبه n
اما درج از مرتبه logn
بخاطر همین گزینه ۲ رو انتخاب کرده. پس اینم اشتباهه دیگه. کاهش از چه مرتبه ایه؟؟
اصلا نمیشه به این مدرسان اعتماد کرد... تکلیفش با خودش مشخص نیست!!
(23 بهمن 1392 01:20 ب.ظ)mhd3 نوشته شده توسط: [ -> ]بنطرتون چرا مقسمی گفته حذف یک عنصر دلخواه میشه از مرتبه n؟؟
وقتی شروع کرده BST رو درس بده اولش گفته که حذف یک عنصر دلخواه از درخت هیپ با n عنصر برابر n است. این زمان ارجحیتی نسبت به زمان مورد نیاز برای حذف یک عنصر دلخواه از لیست نامرتب ندارد.
متاسفانه اشتباه گفته
(23 بهمن 1392 01:20 ب.ظ)mhd3 نوشته شده توسط: [ -> ]بعد یه سوال دیگه. تو این عکس:
مدرسان گفته حذف و کاهش از مرتبه n
اما درج از مرتبه logn
بخاطر همین گزینه ۲ رو انتخاب کرده. پس اینم اشتباهه دیگه. کاهش از چه مرتبه ایه؟؟
اصلا نمیشه به این مدرسان اعتماد کرد... تکلیفش با خودش مشخص نیست!!
تو این سوال هم هر سه عمل در زمان logn انجام میشن
کلید سنجش هم گزینه چهاره
اشتباهشون اینه که فکر کردن اول باید بگردن عنصر رو پیدا کنن، بعد حذفش کنن، در حالی که تو صورت سوال خواسته نشده یک عنصر خاص رو حذف کنیم ، گفته یه عنصر دلخواه
(23 بهمن 1392 01:20 ب.ظ)mhd3 نوشته شده توسط: [ -> ]مدرسان گفته حذف و کاهش از مرتبه n
اما درج از مرتبه logn
بخاطر همین گزینه ۲ رو انتخاب کرده. پس اینم اشتباهه دیگه. کاهش از چه مرتبه ایه؟؟
اصلا نمیشه به این مدرسان اعتماد کرد... تکلیفش با خودش مشخص نیست!!
به طور کلی در هرم :
1- MAX-Heapify با مرتبه log n
2- ساخت هرم : n
3- ساخت هرم از طریق درج : n log n
4- Heap Sort : مرتبه n log n
5- درج ، حذف یک کلید ، حذف max و افزایش و کاهش کلید با مرتبه log n
--------------------------------
این لینک هم ببینید بد نیست :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
