(۰۸ دى ۱۳۹۰ ۱۰:۵۳ ق.ظ)homa نوشته شده توسط:  اگر وزن همه‌ی یال‌ها در گراف اعدادی در بازه‌ی ۲ تا V (تعداد راس) باشد سرعت اجرای الگوریتم kruskal چقدر است؟

با فرض فوق زمان اجرا $o(E\alpha (V))$ میشه
البته شما تعداد راس رو محدود کردید پس زمان اجرا از مرتبه (O(1 هست چون تعداد ثابتی گره در نظر گرفتید اما در حالت کلی اگه بازه وزن یالها اعداد صحیح باشد مرتبه اون خطی بر حسب تعداد یال هست.

(۰۸ دى ۱۳۹۰ ۱۱:۲۵ ق.ظ)Masoud05 نوشته شده توسط:  

(08 دى ۱۳۹۰ ۱۰:۵۳ ق.ظ)homa نوشته شده توسط:  اگر وزن همه‌ی یال‌ها در گراف اعدادی در بازه‌ی ۲ تا V (تعداد راس) باشد سرعت اجرای الگوریتم kruskal چقدر است؟

با فرض فوق زمان اجرا خطی بر حسب تعداد یال خواهد بود (O(e
البته شما تعداد راس رو محدود کردید پس زمان اجرا از مرتبه (O(1 هست چون تعداد ثابتی گره در نظر گرفتید اما در حالت کلی اگه بازه وزن یالها اعداد صحیح باشد مرتبه اون خطی بر حسب تعداد یال هست.

میشه بیشتر توضیح بدین چرا خطی میشه؟؟؟؟من متوجه نمیشم؟؟؟
راس‌ها محدود شدن ولی یال‌ها که محدود نیستن و الگوریتم کراسکال بر حست یال‌ها کار میکنه ..و اولش باید یال‌ها رو بر حسب وزن مرتب کنه و این خودش eloge زمان می خاد

سلام.
توی حالت اول که از مرتب سازی شمارشی استفاده کردید گفتید پیچیدگی خطی هستش درست یعنی o(e) ‌، میشه بگید وجود یا عدم وجود دور در گراف را با چه الگوریتمی بدست آوردید(پیچیدگی اش چیه)؟
خیلی ممنون.

(۱۰ دى ۱۳۹۰ ۰۸:۴۷ ق.ظ)Mojtaba نوشته شده توسط:  سلام.
توی حالت اول که از مرتب سازی شمارشی استفاده کردید گفتید پیچیدگی خطی هستش درست یعنی o(e) ‌، میشه بگید وجود یا عدم وجود دور در گراف را با چه الگوریتمی بدست آوردید(پیچیدگی اش چیه)؟
خیلی ممنون.

به تعداد یال‌ها بررسی میکنیم که ایا با افزودن یال مورد بررسی دور تشکیل می شود یا نه‌، این بررسی به زمان (O(1 برای هر یال نیاز دارد( مجموعه های مجزا که نمی دونم چطوریه‌! )پس در کل یه حلقه داریم که e بار شرط وجود دور را در هر بار با زمان (O(1 انجام میدهد‌، پس در مجموع عمل بررسی دور در زمان $o(E\alpha (V))$ انجام میشه . البته مقدار الفا یه مقدار کوچیکه که نمیدونم خطی حساب میشه یا نه ولی خیلی مقدارش کمه

من فکر نمیکنم پیدا کردن وجود حلقه رو بشه با زمان خطی انجام داد.
جواب زیر رو از اینترنت پیدا کردم و به نظرم همین جواب درسته

(۱۲ دى ۱۳۹۰ ۱۱:۴۳ ب.ظ)homa نوشته شده توسط:  من فکر نمیکنم پیدا کردن وجود حلقه رو بشه با زمان خطی انجام داد.
جواب زیر رو از اینترنت پیدا کردم و به نظرم همین جواب درسته

یه نکته توی کتاب پوران هست( صفحه ۲۲۰ چاپ ۸۹ )که با شرطی که گفتم میگه کراسکال مرتبه زمانیش $o(E\alpha (V))$ . بررسی میکنم اگه خطی حساب شد میگم .
اینم سند‌:

دوستان‌، نظر آقای هادی یوسفی اینه که این الگوریتم با مفروضات فوق خطیه .
پاسخ ایشون‌: " بله در این حالت مرتبه رو میشه خطی فرض کرد "