اگر وزن همه‌ی یالها در گراف اعدادی در بازه‌ی ۲ تا V (تعداد راس) باشد سرعت اجرای الگوریتم kruskal چقدر است؟
(۰۸ دى ۱۳۹۰ ۱۰:۵۳ ق.ظ)homa نوشته شده توسط: اگر وزن همه‌ی یالها در گراف اعدادی در بازه‌ی ۲ تا V (تعداد راس) باشد سرعت اجرای الگوریتم kruskal چقدر است؟با فرض فوق زمان اجرا [tex]o(E\alpha (V))[/tex] میشه
البته شما تعداد راس رو محدود کردید پس زمان اجرا از مرتبه (O(1 هست چون تعداد ثابتی گره در نظر گرفتید اما در حالت کلی اگه بازه وزن یالها اعداد صحیح باشد مرتبه اون خطی بر حسب تعداد یال هست.
(۰۸ دى ۱۳۹۰ ۱۱:۲۵ ق.ظ)Masoud05 نوشته شده توسط:میشه بیشتر توضیح بدین چرا خطی میشه؟؟؟؟من متوجه نمیشم؟؟؟(08 دى ۱۳۹۰ ۱۰:۵۳ ق.ظ)homa نوشته شده توسط: اگر وزن همه‌ی یالها در گراف اعدادی در بازه‌ی ۲ تا V (تعداد راس) باشد سرعت اجرای الگوریتم kruskal چقدر است؟با فرض فوق زمان اجرا خطی بر حسب تعداد یال خواهد بود (O(e
البته شما تعداد راس رو محدود کردید پس زمان اجرا از مرتبه (O(1 هست چون تعداد ثابتی گره در نظر گرفتید اما در حالت کلی اگه بازه وزن یالها اعداد صحیح باشد مرتبه اون خطی بر حسب تعداد یال هست.
راس‌ها محدود شدن ولی یالها که محدود نیستن و الگوریتم کراسکال بر حست یالها کار میکنه ..و اولش باید یالها رو بر حسب وزن مرتب کنه و این خودش eloge زمان می خاد
(۰۸ دى ۱۳۹۰ ۱۱:۵۴ ق.ظ)homa نوشته شده توسط: میشه بیشتر توضیح بدین چرا خطی میشه؟؟؟؟من متوجه نمیشم؟؟؟
راس‌ها محدود شدن ولی یالها که محدود نیستن و الگوریتم کراسکال بر حست یالها کار میکنه ..و اولش باید یالها رو بر حسب وزن مرتب کنه و این خودش eloge زمان می خاد
اگه بتونین با یه الگوریتمی مثل مرتب سازی شمارشی یالها رو در زمان خطی مرتب کنید، مرتبه زمانی کراسکال [tex]o(E\alpha (V))[/tex]خواهد بود والا eloge میشه( بخاطر همین مرتب سازی )
در ضمن تعداد راس‌ها اگه محدود بشه تعداد یالها هم محدود میشه دیگه - نهایتاً یک گراف کاملاً همبند داریم -
سلام.
توی حالت اول که از مرتب سازی شمارشی استفاده کردید گفتید پیچیدگی خطی هستش درست یعنی o(e) ، میشه بگید وجود یا عدم وجود دور در گراف را با چه الگوریتمی بدست آوردید(پیچیدگی اش چیه)؟
خیلی ممنون.
(۱۰ دى ۱۳۹۰ ۰۸:۴۷ ق.ظ)Mojtaba نوشته شده توسط: سلام.به تعداد یالها بررسی میکنیم که ایا با افزودن یال مورد بررسی دور تشکیل می شود یا نه، این بررسی به زمان (O(1 برای هر یال نیاز دارد( مجموعه های مجزا که نمی دونم چطوریه! )پس در کل یه حلقه داریم که e بار شرط وجود دور را در هر بار با زمان (O(1 انجام میدهد، پس در مجموع عمل بررسی دور در زمان [tex]o(E\alpha (V))[/tex] انجام میشه . البته مقدار الفا یه مقدار کوچیکه که نمیدونم خطی حساب میشه یا نه ولی خیلی مقدارش کمه
توی حالت اول که از مرتب سازی شمارشی استفاده کردید گفتید پیچیدگی خطی هستش درست یعنی o(e) ، میشه بگید وجود یا عدم وجود دور در گراف را با چه الگوریتمی بدست آوردید(پیچیدگی اش چیه)؟
خیلی ممنون.
من فکر نمیکنم پیدا کردن وجود حلقه رو بشه با زمان خطی انجام داد.
جواب زیر رو از اینترنت پیدا کردم و به نظرم همین جواب درسته
(۱۲ دى ۱۳۹۰ ۱۱:۴۳ ب.ظ)homa نوشته شده توسط: من فکر نمیکنم پیدا کردن وجود حلقه رو بشه با زمان خطی انجام داد.
جواب زیر رو از اینترنت پیدا کردم و به نظرم همین جواب درسته
یه نکته توی کتاب پوران هست( صفحه ۲۲۰ چاپ ۸۹ )که با شرطی که گفتم میگه کراسکال مرتبه زمانیش [tex]o(E\alpha (V))[/tex] . بررسی میکنم اگه خطی حساب شد میگم .
اینم سند:
[attachment=2217]
(۱۳ دى ۱۳۹۰ ۱۲:۱۷ ق.ظ)Masoud05 نوشته شده توسط:من کتاب پوران ندارم..(12 دى ۱۳۹۰ ۱۱:۴۳ ب.ظ)homa نوشته شده توسط: من فکر نمیکنم پیدا کردن وجود حلقه رو بشه با زمان خطی انجام داد.
جواب زیر رو از اینترنت پیدا کردم و به نظرم همین جواب درسته
یه نکته توی کتاب پوران هست( صفحه ۲۲۰ چاپ ۸۹ )که با شرطی که گفتم میگه کراسکال مرتبه زمانیش خطیه.
اینم سند:
ولی همینی که گذاشتین هم داره میگه زمانش خطی نیست چون آخرش نوشته زمان اجرای کل میشه:[tex]o(E\alpha (V))[/tex]
که مقدار [tex]\alpha (V)[/tex] یک زمان خطی نیست اگه تو کتاب CLRS نگاه کنین این رو گفته
(۱۳ دى ۱۳۹۰ ۱۲:۴۹ ق.ظ)homa نوشته شده توسط: ولی همینی که گذاشتین هم داره میگه زمانش خطی نیست چون آخرش نوشته زمان اجرای کل میشه:[tex]o(E\alpha (V))[/tex]
که مقدار [tex]\alpha (V)[/tex] یک زمان خطی نیست اگه تو کتاب CLRS نگاه کنین این رو گفته
مقدار [tex]\alpha (V)[/tex] یه مقدار بسیار کوچک هست( صفحه ۵۷۴ pdf ویراست ۳ )که در e ضرب شده، . طبق کتاب پوران [tex]\alpha (V)[/tex] برای اعداد بزرگ کمتر از ۴ است!( نمیدونم در کل خطی حساب میشه یا نه )
دوستان، نظر آقای هادی یوسفی اینه که این الگوریتم با مفروضات فوق خطیه .
پاسخ ایشون: " بله در این حالت مرتبه رو میشه خطی فرض کرد "