زمان کنونی: ۲۰ آذر ۱۳۹۷, ۰۶:۳۴ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سرعت اجرای الگوریتم کراسکال

ارسال:
  

homa پرسیده:

سرعت اجرای الگوریتم کراسکال

اگر وزن همه‌ی یال‌ها در گراف اعدادی در بازه‌ی ۲ تا V (تعداد راس) باشد سرعت اجرای الگوریتم kruskal چقدر است؟

۰
ارسال:
  

Masoud05 پاسخ داده:

RE: سرعت اجرای الگوریتم

(۰۸ دى ۱۳۹۰ ۱۰:۵۳ ق.ظ)homa نوشته شده توسط:  اگر وزن همه‌ی یال‌ها در گراف اعدادی در بازه‌ی ۲ تا V (تعداد راس) باشد سرعت اجرای الگوریتم kruskal چقدر است؟
با فرض فوق زمان اجرا [tex]o(E\alpha (V))[/tex] میشه
البته شما تعداد راس رو محدود کردید پس زمان اجرا از مرتبه (O(1 هست چون تعداد ثابتی گره در نظر گرفتید اما در حالت کلی اگه بازه وزن یالها اعداد صحیح باشد مرتبه اون خطی بر حسب تعداد یال هست.

ارسال:
  

homa پاسخ داده:

RE: سرعت اجرای الگوریتم

(۰۸ دى ۱۳۹۰ ۱۱:۲۵ ق.ظ)Masoud05 نوشته شده توسط:  
(08 دى ۱۳۹۰ ۱۰:۵۳ ق.ظ)homa نوشته شده توسط:  اگر وزن همه‌ی یال‌ها در گراف اعدادی در بازه‌ی ۲ تا V (تعداد راس) باشد سرعت اجرای الگوریتم kruskal چقدر است؟
با فرض فوق زمان اجرا خطی بر حسب تعداد یال خواهد بود (O(e
البته شما تعداد راس رو محدود کردید پس زمان اجرا از مرتبه (O(1 هست چون تعداد ثابتی گره در نظر گرفتید اما در حالت کلی اگه بازه وزن یالها اعداد صحیح باشد مرتبه اون خطی بر حسب تعداد یال هست.
میشه بیشتر توضیح بدین چرا خطی میشه؟؟؟؟من متوجه نمیشم؟؟؟
راس‌ها محدود شدن ولی یال‌ها که محدود نیستن و الگوریتم کراسکال بر حست یال‌ها کار میکنه ..و اولش باید یال‌ها رو بر حسب وزن مرتب کنه و این خودش eloge زمان می خاد
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

Mojtaba پاسخ داده:

سرعت اجرای الگوریتم کراسکال

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

ارسال:
  

Masoud05 پاسخ داده:

RE: سرعت اجرای الگوریتم کراسکال

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

۰
ارسال:
  

homa پاسخ داده:

RE: سرعت اجرای الگوریتم کراسکال

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


فایل‌(های) پیوست شده

ارسال:
  

Masoud05 پاسخ داده:

RE: سرعت اجرای الگوریتم کراسکال

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

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

یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

Masoud05 پاسخ داده:

RE: سرعت اجرای الگوریتم کراسکال

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



پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close