سلام
دوستان عزیز این سوال هر کسی میفهمه به منم بگه؟؟
جواب گزینه ۳ هست.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
شما درسنامه مربوطه رو توی کتاب پوران بخوندید
یه الگوریتم هست که به روش تقسیم و حل میاد این زرب رو توی مرتبه ی خوبی انجام میده. الان اینجا B نصف ضریباش صفر هستش.
اگه شما به متن درس دقت کنی میبینید که ظرب [tex]C = A \times B[/tex] رو ما میایم به 3تا ضرب کوچکتر تبدیل میکنیم(یه جوریایی شبیه استراسن) که مثلا اگه سایز A باشه n و همین طور سایز B هم باشه n ما در مرحله بعد میایم همی روال رو روی اون 3 تا ضرب کوچکتر اعمال میکنیم که سایزشون n/2 هستش.
حالا اینجا b نصف ضریباش رو توی مرحله اول نداره یعنی 0 هستن، سوال اینه که ایا با این شرایط میشه ضرب رو سریع تر انجام داد یا نه؟ جواب این میشه که فرقی نمیکنه!
دلیلش هم اینه که ما مثلا توی مرحله اول شاید تعداد زیر مسئله ها مون کم باشه (اونم به این دلیل که زیر مسئله هامون کمتره چو B نصفش صفره) ولی توی مرحله های بعدی الگوریتم دیگه هیچ شرایط خاصی وجود نداره و همه ی زیر مسئله هامون (همون n /2) ها همشون ضرایبشون رو دارن و الگوریتم به صورت کامل روشون اجرا میشه.
در واقع کل حرفام اینه که فقط توی مرحله اول ممکنه کار کمتری انجام بشه ولی توی مراحل بعدی هیچ فرقی در اندازه های مسئله بوجود نمیاد. و هزینه ثابته.
توضیحاتتون خیلی خوب فقط در مورد پیچدگیشم بگید چرا (o(log2 ؟
ممنونم از شما
(11 آذر 1392 11:12 ب.ظ)tarane1992 نوشته شده توسط: [ -> ]توضیحاتتون خیلی خوب فقط در مورد پیچدگیشم بگید چرا (o(log2 ؟
ممنونم از شما
اینم قضیه مستر میشه دیگه!
[tex]t(n) = 3 t(n/2) \Theta(n)[/tex]
حالا [tex]f(n) \in \mathcal{O}(n^ {\log_2 3})[/tex] و همین طور [tex]g(n) \in \Theta(n)[/tex] طبق این قضیه جواب این رابطه میشه [tex]f(n) \in \mathcal{O}(n^ {\log_2 3})[/tex]
نه جواب گزینه 3 هست پیچدیگیش اون نیست که میگید نگاه گنید دوباره سوال.
(12 آذر 1392 11:08 ب.ظ)tarane1992 نوشته شده توسط: [ -> ]نه جواب گزینه ۳ هست پیچدیگیش اون نیست که میگید نگاه گنید دوباره سوال.
پوران گزینه 2 رو انتخاب کرده.