سلام دوستان.
می خواستم جواب سوال ۱۶ ساختمان داده دکتری ۹۱ را بدونم. من بین گزینه ۳ و ۴ شک دارم.[/align]
در یک داده ساختار مجموعه های مجزا "distinct sets" که با درخت و بدون فشرده سازی مسیرپیاده سازی شده است و در عمل ادغام درخت با ارتفاع کمتر فرزند درخت با ارتفاع بیشتر می شود. اگر تعداد عناصر n باشد هزینه دنباله ای از m عمل ادغام و f عمل یافتن حداکثر چقدر است؟
۱- O(f+m)
۲- O(f+m lg n)
۳- O(m+f lg n)
۴- O((f+m) lg n)
صبر کن امسال ارشد قبول شیم بعد دوسال بعدش جوابتو میدیم
))
(۱۴ بهمن ۱۳۹۱ ۰۲:۴۸ ب.ظ)barbados2500 نوشته شده توسط: سلام دوستان.
می خواستم جواب سوال ۱۶ ساختمان داده دکتری ۹۱ را بدونم. من بین گزینه ۳ و ۴ شک دارم.[/align]
در یک داده ساختار مجموعه های مجزا "distinct sets" که با درخت و بدون فشرده سازی مسیرپیاده سازی شده است و در عمل ادغام درخت با ارتفاع کمتر فرزند درخت با ارتفاع بیشتر می شود. اگر تعداد عناصر n باشد هزینه دنباله ای از m عمل ادغام و f عمل یافتن حداکثر چقدر است؟
۱- O(f+m)
۲- O(f+m lg n)
۳- O(m+f lg n)
۴- O((f+m) lg n)
سلام دوست عزیز
سوال بسیار ساده است. در درخت ها ادغام هزینه O(1 دارد و ان تا ادغام می شه او ان و برای یافتن یک عنصر باید O(lg مصرف کنی و برای یافتن ان عنصر باید O(nlgn
در نتیجه جواب گزینه سوم است
موفق باشید