(۱۰ بهمن ۱۳۹۰ ۱۲:۵۶ ق.ظ)homa نوشته شده توسط:  

(05 بهمن ۱۳۹۰ ۰۲:۱۸ ق.ظ)rad.bahar نوشته شده توسط:  

اینجا تمام ماتریس‌ها با هم برابر ند چون همه رو با متغیر A مشخص کرده و اندیس کنارشون فقط اندازه‌ی اونها رو نشون میده و همین طور گفته:
[tex]A_{0}=[1][/tex]
و در مورد:
[tex]A_{1}=\begin{bmatrix} 1 &1 \\ 1& 1 \end{bmatrix}[/tex]
[tex]A_{1}=\begin{bmatrix} 1 &1 &1 &1 \\ 1 & 1 & 1 & 1\\ 1& 1 & 1 &1 \\ 1 & 1 & 1& 1 \end{bmatrix}[/tex]

تو مسائلی که بخایم مرتبه زمانی بدست بیاریم معمولا باید بهترین راه حل رو انتخاب کنیم:
حالا با توجه به شکلی که گذاشته بودی ومنم اینجا پیوست کردم:
A1 با A2 تو ماتریس برابر ند پس من میتونم فاکتور گیری رو انجام بدم که میشه:

[tex]A_{1}(V_{1} V_{2})[/tex] یا [tex]A_{2}(V_{1} V_{2})[/tex]

اینجا من یک ضرب دارم و یک جمع
زمان جمع به n/2 نیاز داره و ضرب هم میشه:

[tex]T(\frac{n}{2})[/tex]

برای قسمت پایین هم همینه پس کلا داریم:
[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{2}) (\frac{n}{2} \frac{n}{2})=2T(\frac{n}{2}) n[/tex]


که برابر هست با: nlogn

(۰۵ بهمن ۱۳۹۰ ۰۲:۱۸ ق.ظ)rad.bahar نوشته شده توسط:  ماتریس های Ak ماتریسی به شکل ۲ به توان k در ۲ به توان k است و v برداری ستونی به طول
n = 2^k است برای ضرب Ak.V زمان مصرفی چقدر است
جواب:nlogn
راه حلی که استفاده کردم اینه
اگر از روش تقسیم و غلبه استفاده کنیم ماتریس Ak باید ۴ تکه و ماتریس V دو تکه شوند در صرب این ۴ تکه در ۲ تکه ۴ ارایه ۲ به توان k-1 در ۲ به توان k-1 ایجاد می شود ۲ تا از ارایه‌ها با هم و ۲ تا دیگرشان با هم جمع می شوند که از مرتبه طول v یعنی n است
پس رابطه بازگشتی برابر t(n) =4t(n/2) + n است ولی جواب حاصل از مرتبه n^2 است
ایا راهی هست که از مرتبه nlogn باشد؟

لطفا جواب بدید