ماتریس های 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 باشد؟
لطفا جواب بدید
(۰۵ بهمن ۱۳۹۰ ۰۲:۱۸ ق.ظ)rad.bahar نوشته شده توسط: ماتریس های Ak ماتریسی به شکل ۲ به توان k در ۲ به توان k است و v برداری ستونی به طولروشت کاملا درسته اما جایی که اشتباه کردی اینه که تمام ۴ مولفه که بدست اوردی رو با هم جمع میکنی در صورتی که جوابی که بدست میاد یک ماتریس ستونی هست با n مولفه یعنی همون ۲ به توان k.
n = 2^k است برای ضرب Ak.V زمان مصرفی چقدر است
جواب:nlogn
راه حلی که استفاده کردم اینه
اگر از روش تقسیم و غلبه استفاده کنیم ماتریس Ak باید ۴ تکه و ماتریس V دو تکه شوند در صرب این ۴ تکه در ۲ تکه ۴ ارایه ۲ به توان k-1 در ۲ به توان k-1 ایجاد می شود ۲ تا از ارایه‌ها با هم و ۲ تا دیگرشان با هم جمع می شوند که از مرتبه طول v یعنی n است
پس رابطه بازگشتی برابر t(n) =4t(n/2) + n است ولی جواب حاصل از مرتبه n^2 است
ایا راهی هست که از مرتبه nlogn باشد؟
لطفا جواب بدید
پس فقط کافیه ۲ تا مولفه هایی که از ضرب سطر بالایی ماتریس n*n در ماتریس ستونی بدست اومده با هم جمع کنی.
که میشه:
[tex]T(n)=2T(\frac{n}{2}) O(n)[/tex]
پس همون --->
[tex]O(nlogn)[/tex]
با تشکر ار جوابتان ولی متوحه نشدم
به نظر من ۲ تا از ۴ مولفه حاصل با هم و ۲ تای دیگر با هم جمع می شوند شکلی ضمبمه کردم تا راه حل را ببینید در اینحا ۴ مولفه A1*V1 , A2*V2 , A3*V1 , A4*V2 داریم که برای به دست اوردن
ماتریس ستونی حاصل از ضرب به ۲ جمع زیر نیاز داریم
A1*V1 + A2*V2 , A3*V1 + A4*V2
نتیحه حاصل اینکه یه ۴ فراخوانی بازگشتی ضرب N/2 در N/2 نیاز داریم
لطفا بگویید کجا را اشتباه می کنم
(۰۵ بهمن ۱۳۹۰ ۰۲:۱۸ ق.ظ)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 باشد؟
لطفا جواب بدید
اینجا تمام ماتریس‌ها با هم برابر ند چون همه رو با متغیر 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
(۱۰ بهمن ۱۳۹۰ ۱۲:۵۶ ق.ظ)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
ممنون از جوابتان
با این حساب A1 و A2 و A3 و A4 با هم برابرند پس کافبه مثلا A1(V1+V2 را حساب کرد و تنها با همین مقدار نتیجه را به دست اورد
به شمل ضمیمه نگاه کنید
پس یعنی یک ضرب و یک جمع
T(n )= T(n/2)+n
که میشه از مرتبه n
لطفا بگویید کجا را اشتباه می کنم
(۱۰ بهمن ۱۳۹۰ ۱۱:۳۳ ق.ظ)rad.bahar نوشته شده توسط: با این حساب A1 و A2 و A3 و A4 با هم برابرند پس کافبه مثلا A1(V1+V2 را حساب کرد و تنها با همین مقدار نتیجه را به دست اورد
به شمل ضمیمه نگاه کنید
پس یعنی یک ضرب و یک جمع
T(n )= T(n/2)+n
که میشه از مرتبه n
لطفا بگویید کجا را اشتباه می کنم
اشتباهت اونجاست که تو بردار ستونی که بدست میاد مقدار پایینی با مقدار بالایی برابر نیست که بخای با بدست اوردن یکی اونیکی هم بدست اومده باشه:
[tex]\begin{bmatrix} A_{k-1}(V_{1} V_{2})\\ A_{k-1}(V_{1}-V_{2}) \end{bmatrix}[/tex]
(ولی اگر مساوی بودند همون مرتبه‌ی n میشد)