سرعت الگوریتم کروسکال در گراف شلوغ از پریم کمتره یا مساوین؟
پوران میگه کمتره (یعنی پریم سریعتره) ۶۰۰ مساله میگه مساوین
با تشکر
سلام
میشه بگید کدوم صفجه از ۶۰۰ مسله این رو گفته ؟
اره خوب درسته
هزینه بالایی رو باید داد برای مرتب سازی
چون مرتبه گراف از درجه دو میشه
E ~ n^2
سلام
سوال ۷۰ فصل ۶ رو ببینید
پاسخ تشریحیشو هم بخونید شاید من بد متوجه شدم
اگ در دسترس نیست بگید عکسشو بذارم
من فک میکنم از نظر پیچیدگی مساوین ولی تو ضرایب کراسکال بهتره.
ادامه سوالشم بخونید گفته پریم از باینری هیپ استفاده میکنه که میشه از مرتبه e log n که با کراسکال یکی میشه یعنی دیگه پریم از مرتبه n^2 نیست پس از یک مرتبه میشن
مرسی
بله درست میگید.
به اینکه با هیپ دوجمله ای هست دقت نکردم.
پس نتیجه این شد ک اگه با هیپ فیبوناچی صف اولویت در پریم رو ساخته باشه پریم سریعتره ولی الان چون با هیپ دوجمله ای ساخته شده سرعتشون یکیه ( در گراف شلوغ )
ممنون از همه
شایدم بشه گفت اگه گراف کامل باشه تعداد یال ها مرتبه ۲ داره اونوقت با ۲^n پریم یکی میشه
۲ تا نکته که کلا بشه این مبحث رو جمع کرد
۱- اگر گراف با ماتریس پیاده شود آنگاه اگر خلوت باشد کراسکال بهتر است و اگر متراکم باشد پریم بهتر است
۲- اگر گراف با لیست پیاده سازی شود ، پیاده سازی از پریم وجود دارد که همیشه از کراسکال بهتر است
ممنون
جدای از جواب این سوال،، این نکته ی دوم ک نوشتید واقعا برای من سواله
پیاده سازی پریم با استفاده از نمایش گراف به صورت ماتریس مجاورت [tex]O(v^2)[/tex] زمان می‌بره. بااستفاده از داده ساختار هیپ دودوئی ساده و نمایش فهرست مجاورت در زمان [tex]o(elogv)[/tex]است. استفاده از هیپ فیبوناچی [tex]o(e \: vlogv)[/tex]
ک اگ گراف خلوت باشه کروسکال [tex]o(elogv)[/tex] میشه ک دیگه فوقش با هم مساوین
. میشه بپرسم شما از روی چی این نکته رو میگید؟ من ک هر چی کتاب دیدم میگن در گراف خلوت کراسکال بهتر عمل میکنه
(۰۳ بهمن ۱۳۹۳ ۰۲:۳۱ ب.ظ)nazanin2020 نوشته شده توسط: ممنون
جدای از جواب این سوال،، این نکته ی دوم ک نوشتید واقعا برای من سواله
پیاده سازی پریم با استفاده از نمایش گراف به صورت ماتریس مجاورت [tex]O(v^2)[/tex] زمان می‌بره. بااستفاده از داده ساختار هیپ دودوئی ساده و نمایش فهرست مجاورت در زمان [tex]o(elogv)[/tex]است. استفاده از هیپ فیبوناچی [tex]o(e \: vlogv)[/tex]
ک اگ گراف خلوت باشه کروسکال [tex]o(elogv)[/tex] میشه ک دیگه فوقش با هم مساوین
منبع ۲ تا نکته که گفتم کلاس آقای یوسفی بود
خودشون سریحا این جملات رو قید کردن و توضیحی ندادند
اما نظر من اینه که چون e log e مرتبه کراسکال به خاطر مرتب سازی یال هاست و مرتب سازی حداقل n log n است و گاهی بیشتر
اما مرتبه هیپ حداکثر n log n و گاهی کمتر میشه پس پریم با هیپ همیشه میتونه مرتبه خوبی داشته باشه
(این نظر منه، دوستان که از من وارد ترن تو درستی یا نادرستی این جمله اظهار نظر کنند)
(۰۳ بهمن ۱۳۹۳ ۱۰:۴۰ ب.ظ)L3ic نوشته شده توسط: منبع ۲ تا نکته که گفتم کلاس آقای یوسفی بود
خودشون سریحا این جملات رو قید کردن و توضیحی ندادند
اما نظر من اینه که چون e log e مرتبه کراسکال به خاطر مرتب سازی یال هاست و مرتب سازی حداقل n log n است و گاهی بیشتر
اما مرتبه هیپ حداکثر n log n و گاهی کمتر میشه پس پریم با هیپ همیشه میتونه مرتبه خوبی داشته باشه
(این نظر منه، دوستان که از من وارد ترن تو درستی یا نادرستی این جمله اظهار نظر کنند)
من تا به حال اینو نشنیده بودم
پس حداقل حتما باید توی صورت سوال بگن با چی ساخته شده
اگه نگن بنظر من باید پیش فرض رو همون e logv در نظر بگیریم .