سلام
مقسمی تو درسنامش گفته مرتبه حذف یک عنصر دلخواه ار درخت هیپ با n عنصر برابر (O( n
اما تست ۴۲ آی تی ۹۰ گفته یک maxheap با n عنصر را که در آرایه [ A [1..n
قرار دارد در نظر بگیرید، مرتبه زمانی الگوریتم حذف عنصر i ام از این ماکس هیپ به گونه ای که ساختار ماکس هیپ را حفظ کند چیست؟
جوابشم گفته nlogn
الان کدوم درسته؟؟ حذف عنصر i ام با حذف یک عنصر دلخواه فرق داره مگه؟؟
فکر کنم کلیدتون اشتباست ، برای من جوابو نوشته logn
کلا مرتبه حذف عنصر از هیپ میشه logn
کافیه گره حذف بشه و یک بار Max-Heapify فراخوانی بشه. که اینم میشه log n
نه اتفاقا من با nlogn کاملا موافقم.
ببینید منطقش اینه: چون نمیتونیم از وسط هیپ گرهی رو حذف کنیم باید انقدر از بالا (ریشه) حذف کنیم تا برسیم به اون گره دلخواه دیگه. بعد میتونیم اون گره دلخواه رو حذف کنیم. پس در بدترین حالت میشه از مزتبه nlogn
چون خود حذف که logn میشه، حالا در بدترین حالت برای حذف عنصر i ام باید n بار حذف کنیم و مرتب کنیم که میشه nlogn
من نمیدونم پس چرا مقسمی گفته n!!!
اینجا رو ببینین
(۲۳ بهمن ۱۳۹۲ ۱۲:۰۸ ب.ظ)tayebe68 نوشته شده توسط: اینجا رو ببینین
کجا رو دقیقا؟؟
واسه من چیزی نیومده!
الان شما با این منطقی که مدرسان آورده مخالفین؟؟با nlogn ؟؟
(۲۳ بهمن ۱۳۹۲ ۱۲:۳۴ ب.ظ)mhd3 نوشته شده توسط:(23 بهمن ۱۳۹۲ ۱۲:۰۸ ب.ظ)tayebe68 نوشته شده توسط: اینجا رو ببینین
کجا رو دقیقا؟؟
واسه من چیزی نیومده!
الان شما با این منطقی که مدرسان آورده مخالفین؟؟با nlogn ؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۲۳ بهمن ۱۳۹۲ ۱۲:۴۳ ب.ظ)tayebe68 نوشته شده توسط:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مرسی. خیلی ممنونم.
فقط یه سوال کوچولو. بنطرتون چرا مقسمی گفته حذف یک عنصر دلخواه میشه از مرتبه n؟؟
وقتی شروع کرده BST رو درس بده اولش گفته که حذف یک عنصر دلخواه از درخت هیپ با n عنصر برابر n است. این زمان ارجحیتی نسبت به زمان مورد نیاز برای حذف یک عنصر دلخواه از لیست نامرتب ندارد.
---------------------------
بعد یه سوال دیگه. تو این عکس:
[attachment=15376]
مدرسان گفته حذف و کاهش از مرتبه n
اما درج از مرتبه logn
بخاطر همین گزینه ۲ رو انتخاب کرده. پس اینم اشتباهه دیگه. کاهش از چه مرتبه ایه؟؟
اصلا نمیشه به این مدرسان اعتماد کرد... تکلیفش با خودش مشخص نیست!!
(۲۳ بهمن ۱۳۹۲ ۰۱:۲۰ ب.ظ)mhd3 نوشته شده توسط: بنطرتون چرا مقسمی گفته حذف یک عنصر دلخواه میشه از مرتبه n؟؟متاسفانه اشتباه گفته
وقتی شروع کرده BST رو درس بده اولش گفته که حذف یک عنصر دلخواه از درخت هیپ با n عنصر برابر n است. این زمان ارجحیتی نسبت به زمان مورد نیاز برای حذف یک عنصر دلخواه از لیست نامرتب ندارد.
(۲۳ بهمن ۱۳۹۲ ۰۱:۲۰ ب.ظ)mhd3 نوشته شده توسط: بعد یه سوال دیگه. تو این عکس:تو این سوال هم هر سه عمل در زمان logn انجام میشن
مدرسان گفته حذف و کاهش از مرتبه n
اما درج از مرتبه logn
بخاطر همین گزینه ۲ رو انتخاب کرده. پس اینم اشتباهه دیگه. کاهش از چه مرتبه ایه؟؟
اصلا نمیشه به این مدرسان اعتماد کرد... تکلیفش با خودش مشخص نیست!!
کلید سنجش هم گزینه چهاره
اشتباهشون اینه که فکر کردن اول باید بگردن عنصر رو پیدا کنن، بعد حذفش کنن، در حالی که تو صورت سوال خواسته نشده یک عنصر خاص رو حذف کنیم ، گفته یه عنصر دلخواه
(۲۳ بهمن ۱۳۹۲ ۰۱:۲۰ ب.ظ)mhd3 نوشته شده توسط: مدرسان گفته حذف و کاهش از مرتبه nبه طور کلی در هرم :
اما درج از مرتبه logn
بخاطر همین گزینه ۲ رو انتخاب کرده. پس اینم اشتباهه دیگه. کاهش از چه مرتبه ایه؟؟
اصلا نمیشه به این مدرسان اعتماد کرد... تکلیفش با خودش مشخص نیست!!
۱- MAX-Heapify با مرتبه log n
۲- ساخت هرم : n
۳- ساخت هرم از طریق درج : n log n
۴- Heap Sort : مرتبه n log n
۵- درج ، حذف یک کلید ، حذف max و افزایش و کاهش کلید با مرتبه log n
--------------------------------
این لینک هم ببینید بد نیست :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خیلی ممنونم از هردوتون
