پیچیدگی زمانی

[yas1213]

نشان دهید الگوریتم تقسیم و حل این عبارت دارای پیچیدگی زمانی نمایی است.i,j,k اندیس اند وmin عبارت داخل_ _ است.

Mij=minimum _Mi,k + MK+1,j + Di-1*Dk*Dj_ ;i<=k<=j ;i<j
عبارت تعداد عمل ضرب ماتریس ها را نشان می دهد که باdynamic programming پیچیدگی n^3 را دارد .

[pesar irooni]

خوب این که معلومه
چون بصورت بازگشتیه اگه فرمولش رو بنویسی و حل کنی جواب نمایی 2^n-1 رو میده.
تو کتاب clrs فصل برنامه سازی پویا هستش.

[yas1213]

پس لطف کنین فرمول بازگشتیشو بذارین!
پیچیدگی 2 به توانn-1 دیگه؟?

[pesar irooni]

دیشب میخواستم براتون بنویسم ولی دیدم نوشتن فرمولای ریاضی تو نت خیلی سخته بیخیال شدم. اما خوب حالا که در خواست کردید مینویسم

T(1) >= 1T(n) >= 1 + zigma k=1 to n-1 {T(k) + T(n-k) + 1} for n > 1

با توجه به اینکه هر عبارت T(i) یکبار بصورت T(k) و یکبار بصورت T(n-k) ظاهر میشود و با جمع کردن n-1 عدد 1 با هم و جمع با 1 خارج از سیگما داریم:

T(n) >= 2 zigma i=1 to n-1 {T(i)} + n

با استفاده از روش جایگذاری داریم :

T(n) >= 2 zigma i=1 to n-1 {2^(i-1)} + n = 2 zigma i=0 to n-2 {2^i} + n = 2 (2^(n-1) - 1 ) + n = (2^n - 2) + n >= 2^(n-1)

[yas1213]

میشه یه ذره بیشتر توضیح بدین!
از کجا فرمول بازگشتیشو اوردین؟؟؟
یعنی از روی الگوریتمش نوشتین؟؟
2 به توان n-1 از کجا اوومد؟؟!!
خط اولشو درست نوشتین؟؟T(1)??

[pesar irooni]

اگه الگوریتم بازگشتیه اونو بنویسی فرمولش به راحتی در میاد دیگه.
2^n-1 هم که از حل فرمول بازگشتی توسط روش جایگذاری که از مباحث فصول اول طراحی الگوریتمه بدست اومد.
اینم فرموله بازگشتیشه:

Rec-Mat-chain(p,i,j)

if i=j then

   return 0

m[i,j] <-- infinite

for k <-- i to j-1 do

      q <-- Rec-Mat-chain(p,i,k) + Rec-Mat-chain(p,k+1,j) + p(i-1) * p(k) * p(j)

      if q < m[i,j] then

           m[i,j] <-- q

return m[i,j]

[Monthly]

کتاب clrs رو می شه بیشتر معرفی کنید؟
یا اگه ebooke به این ادرس ایمیل کنید؟
lihar.parsa@gmail.com
اگه کتابه انتشارات. نویسنده. قیمت و ... را ایمیل کنید.
ممنون

[pesar irooni]

این کتاب نوشته چهار نویسنده (استاد) هست که CLRS مخفف اوایل اسمشونه که اولیش cormen هست.
ترجمه ای از این کتاب که تو بازاره خیلی خوبه و غلط نداره. به رنگ سبز و به ترجمه گروه مهندسی پژوهشی خوارزمی. ebook ش هم تو نت هست. بگردی پیدا میکنی. اما پیشنهاد میکنم کتابش رو بخری.
چاپ 86 قیمتش 6000 تومان بود الان فکر کنم هول و هوش 7 تومن باشه.