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

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

ارسال:
  

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: سرعت اجرای الگوریتم کراسکال

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سرعت روش سیم بندی شده نسبت ریز برنامه ریزی شده mostafaheydar1370 ۰ ۱,۸۱۲ ۱۸ بهمن ۱۳۹۵ ۰۱:۲۰ ب.ظ
آخرین ارسال: mostafaheydar1370
  الگوریتم نوبت گردشی mhasa ۴ ۳,۰۹۳ ۱۴ بهمن ۱۳۹۵ ۱۰:۵۴ ب.ظ
آخرین ارسال: mhasa
  کدهای الگوریتم سولین,کراسکال,پریم mohammad.chavoshipor ۲ ۲,۹۰۸ ۱۴ دى ۱۳۹۵ ۱۰:۰۵ ب.ظ
آخرین ارسال: sam7ariya
  درخواست کمک فوری در مورد اینترنت پر سرعت!!!!! Somayeh_Y ۱۱ ۵,۰۴۴ ۱۳ اسفند ۱۳۹۴ ۰۵:۱۰ ق.ظ
آخرین ارسال: one hacker alone
  سرعت اینترنت خوابگاه دانشگاه امیرکبیر !!! ۱۵ ۸,۳۲۰ ۲۲ اردیبهشت ۱۳۹۴ ۰۹:۳۶ ق.ظ
آخرین ارسال: pouya47
  مشکل سرعت tor s-nowrozi ۱ ۱,۹۲۵ ۲۹ فروردین ۱۳۹۴ ۱۰:۲۳ ب.ظ
آخرین ارسال: one hacker alone
  علت پایین اومدن سرعت کامپیوتر هلیا۹۹ ۵ ۳,۱۳۰ ۱۴ اسفند ۱۳۹۳ ۰۷:۳۸ ب.ظ
آخرین ارسال: one hacker alone
  سرعت SLR مساویه LALR است یا کمتره ؟ ریحان ۴ ۲,۱۱۹ ۱۱ بهمن ۱۳۹۳ ۰۷:۴۱ ب.ظ
آخرین ارسال: ریحان
  نحوه ورود فرایند ها در الگوریتم RR abji22 ۱۳ ۴,۵۰۶ ۲۴ دى ۱۳۹۳ ۱۲:۱۴ ق.ظ
آخرین ارسال: abji22
  راه حل برای بهبود سرعت اینترنت vesta ۸ ۴,۳۷۸ ۲۹ مهر ۱۳۹۳ ۰۶:۵۲ ق.ظ
آخرین ارسال: pesaredelsokhte

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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