mehran2008

مرسی آقا مهدی.

پس اگه موافق باشید، به عنوان اولین مرحله کار، سوالات 4، 10، 11 و 18 رو که مربوط به هزینه های محاسباتی هستند، بررسی کنیم. من سعی می کنم جواب تشریحی این سوالات رو تا جایی که بلدم، تا یکی دو روز آینده اینجا قرار بدم. البته اگه سایت باز بشه برام.

mardin200

دوستان خسته نباشيد. كارتون عاليه
به نظر من به ترتيب سوال جلو بريم بهتر خواهد بود چون بعدا افردي كه بخوان استفاده كنن براشون راحتتره

در مورد سوال 4 عناصر ماتريس توليد شده 1 يا 1- خواهند بود پس هيچ حاصلضربي وجود نخواهد داشت فقط بايد حاصلجمع ها را شمرد . ساده ترين روش كه از مرتبه n^2 خواهد بود. اگر هم تمام عناصر V برابر باشند كه فقط اولين عنصر ماتريس حاصل مقدار دارد بقيه عناصر صفر خواهند شد. يعني الگوريتم از مرتبه n خواهد بود
ولي در سوال عناصر V برابر نيستند. براي ماتريس A تمام عناصر سطر اول 1 خواهد شد و براي بقيه سطرها نصف عناصر 1 و نصف ديگر 1- خواهند بود . من يك الگوريتم با n*n/2 تونستم براش تعريف كنم ولي هرچي زور زدم نتونستم nLog n پيدا كنم.
ولي با توجه به گزينه ها به نظر ميرسه همون nLog n باشه

__________________