سه سوال از ارشد ۹۴ - نسخه‌ی قابل چاپ

سه سوال از ارشد ۹۴ - Sanazzz - 14 خرداد ۱۳۹۸ ۱۰:۱۹ ب.ظ

سلام
عیدتون مبارک
میشه لطفا در مورد این سوالا کمکم کنین
خیلی خیلی خیلییییییییی ممنون میشم
تشکراااات ویژههههه
لطفا اگر کسی حل تشریحی سوال های طراحی الگوریتم ارشد ۹۷ هم داره بزاره
خیلی خیلی ممنون میشم
من خیلی دنبالش گشتم ولی نبود
بی نهایت ممنون میشم کمکم کنین
خدا خیرتون بده

[تصویر: 468392_5oat_p_20190604_011531_vhdr_on_1.jpg]

[تصویر: 468392_5oat_p_20190604_011531_vhdr_on_1.jpg]

[تصویر: 468392_pewo_p_20190604_023713_vhdr_on_1.jpg]

[تصویر: 468392_o03y_p_20190604_221555_vhdr_on_1.jpg]

RE: سه سوال از ارشد ۹۴ - Saman - 19 شهریور ۱۳۹۸ ۰۸:۱۴ ب.ظ

(۱۴ خرداد ۱۳۹۸ ۱۰:۱۹ ب.ظ)Sanazzz نوشته شده توسط: سلام
عیدتون مبارک
میشه لطفا در مورد این سوالا کمکم کنین
خیلی خیلی خیلییییییییی ممنون میشم
تشکراااات ویژههههه
لطفا اگر کسی حل تشریحی سوال های طراحی الگوریتم ارشد ۹۷ هم داره بزاره
خیلی خیلی ممنون میشم
من خیلی دنبالش گشتم ولی نبود
بی نهایت ممنون میشم کمکم کنین
خدا خیرتون بده

جواب سوال ۱۱)
شما وقتی از دکسترا استفاده میکنید هر یال رو دقیقا یک بار relax میکنید.این میشه [tex]O(E)[/tex]
و یه لیست Vتایی دارید که هر بار از اون min میگیرید. این میشه [tex]O(V)[/tex] و این کارو V بار و به عبارتی به تعداد رئوس انجام میدید
حالت عادی این مساله میشه [tex]O(E+V^2)[/tex]

حالا شما ساختمان داده ش رو عوض کردید و توو سوال گفته که من با هیپ فیبوناچی زمان خروج اون گره ی کمتر از لیست رو در زمان [tex]\log\: n[/tex] انجام میدم.(توو سوال خودش گفته زمان minگیری اونقدر هستش)

پس در کل مجوع این دوتا میشه : [tex]O(E\: +\: VlogV)[/tex]

(۱۴ خرداد ۱۳۹۸ ۱۰:۱۹ ب.ظ)Sanazzz نوشته شده توسط: سلام
عیدتون مبارک
میشه لطفا در مورد این سوالا کمکم کنین
خیلی خیلی خیلییییییییی ممنون میشم
تشکراااات ویژههههه
لطفا اگر کسی حل تشریحی سوال های طراحی الگوریتم ارشد ۹۷ هم داره بزاره
خیلی خیلی ممنون میشم
من خیلی دنبالش گشتم ولی نبود
بی نهایت ممنون میشم کمکم کنین
خدا خیرتون بده

نکته ی سوال ۹ اینه : تعداد مراحل این الگوریتم به بررسی ترتیب یال ها وابسته است(رووش فکر کنید جالبه)