سلام
آیا این عبارات درسته؟
۱- درخت متوازن درختیه که تا سطح ماقبل آخر پر باشد.
۲- زمان اجرای مرتب سازی heapsort در بهترین حالت زمانی که عناصر متمایز باشند از مرتبه (big omega(nlogn است.
۳- برتری روش IO MAPPED IO نسبت به MEMORY MAPPED IO : در زمان اجرا نیاز به انتقال داده به حافظه ندارد.
ممنون میشم دوستان اگر با توضیح کافی سوالات رو جواب بدین. چون به صورت کلیدی توی پاسخنامه موجوده.
سلام
۱) درخت متوازن دزختی هست که اختلاف سطح برگ ها حداکثر ۱ باشد. منظور از پر بودن هم اینه که هر گره درخت باید تمامی فرزندان ممکن خودش رو داشته باشد مثلا اگر kتایی هست باید تمامی گره ها k فرزند داشته باشند (به جز برگ ها البته) خب اگر سطح ما قبل آخر(n-1) پر نباشه الزاما به معنی متوازن نبودن نیست مثلا اگر درخت دوتایی باشه در سطح n-2 ممکنه که گرهی فقط یک فرزند داشته باشه پس پر نیست در عین حال متوازن بودن رو هم بهم نزده یعنی باز هم برگ ها یا در سطح آخر هستند یا در سطح ماقبل آخر بنابراین این گزینه الزاما درست نیست.
۲) ساخت یک درخت heap در O(n) امکان پذیر هست بعد از ساخت با توجه به الگوریتم heapsort همواره باید عنصر ماکزیمم(مینیمم در minheap) از راس هیپ حذف شده و به انتهای آرایه ای که هیپ در آن است برود که برای n عنصر حدف از هیپ teta nlogn میشود بنابراین همواره مرتبه nlogn است و بدترین و بهترین حالت نداریم(ذکر شده که عناصر متمایز هستند اگر متمایز نبود و همه یکسان بودند مرتبه teta(n))- در واقع چون هرچی بهش بدیم ابتدا تبدیل به هیپ میکنه بهترین یا بدترین در صورت متمایز بودن عناصر بی معنی هست. اما اگر عناصر هرچی باشه در بدترین حالت O(nlogn)
مرسی. دقیقا جواب خود من همین بوده که شما گفتید. ولی این پارسه همچنان سوالاتش مملو از غلطه!