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

اگه شما به متن درس دقت کنی میبینید که ظرب [tex]C = A \times B[/tex] رو ما میایم به ۳تا ضرب کوچکتر تبدیل میکنیم(یه جوریایی شبیه استراسن) که مثلا اگه سایز A باشه n و همین طور سایز B هم باشه n ما در مرحله بعد میایم همی روال رو روی اون ۳ تا ضرب کوچکتر اعمال میکنیم که سایزشون n/2 هستش.

حالا اینجا b نصف ضریباش رو توی مرحله اول نداره یعنی ۰ هستن، سوال اینه که ایا با این شرایط میشه ضرب رو سریع تر انجام داد یا نه؟ جواب این میشه که فرقی نمیکنه!
دلیلش هم اینه که ما مثلا توی مرحله اول شاید تعداد زیر مسئله ها مون کم باشه (اونم به این دلیل که زیر مسئله هامون کمتره چو B نصفش صفره) ولی توی مرحله های بعدی الگوریتم دیگه هیچ شرایط خاصی وجود نداره و همه ی زیر مسئله هامون (همون n /2) ها همشون ضرایبشون رو دارن و الگوریتم به صورت کامل روشون اجرا میشه.

در واقع کل حرفام اینه که فقط توی مرحله اول ممکنه کار کمتری انجام بشه ولی توی مراحل بعدی هیچ فرقی در اندازه های مسئله بوجود نمیاد. و هزینه ثابته.

توضیحاتتون خیلی خوب فقط در مورد پیچدگیشم بگید چرا (o(log2 ؟

ممنونم از شما

(۱۱ آذر ۱۳۹۲ ۱۱:۱۲ ب.ظ)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]

نه جواب گزینه ۳ هست پیچدیگیش اون نیست که میگید نگاه گنید دوباره سوال.

(۱۲ آذر ۱۳۹۲ ۱۱:۰۸ ب.ظ)tarane1992 نوشته شده توسط:  نه جواب گزینه ۳ هست پیچدیگیش اون نیست که میگید نگاه گنید دوباره سوال.

پوران گزینه ۲ رو انتخاب کرده.