این مرتبه مربوط به روش تقسیم وحله. حالا اگه از روش پویا استفاده کنیم، و حالات رو ذخیره کنیم، مرتبه برابر n میشه

Sent from my SM-T210R using Tapatalk

(۰۹ دى ۱۳۹۲ ۰۸:۴۹ ب.ظ)hoomanab نوشته شده توسط:  
این مرتبه مربوط به روش تقسیم وحله. حالا اگه از روش پویا استفاده کنیم، و حالات رو ذخیره کنیم، مرتبه برابر n میشه

Sent from my SM-T210R using Tapatalk

میشه یه ذره بیشتر توضیح بدین !!!!

توی پیدا کردن بزرگترین زیر آرایه از روش تقسیم و حل، آرایه به دو قسمت تقسیم میشه. یک بار نیمه چپ چک میشه، یک بار نیمه راست، و یک بار قسمتی که مقداریش توی نیمه چپه مقداریش توی نیمه راست. عکس الگوریتم های تقسیم و حلشو پیوست میکنم.
اون مقداری که توی عکس قبلی نشونتون دادم، پیچیدگی زمانی همین روشه تقسیم و حله.
برای روش پویا بزرگترین زیر آرایه ای که به دست آوردیم ذخیره میکنیم توی یک آرایه جدید که جمع بزرگترین زیر آرایه ایه که به عنصر k-ام ختم میشه.
حالا هر دفعه که مقدار جدیدی به دست اومد، یعنی تا عناصر بعد از k پیش رفتیم، مقدار به دست اومده رو با a]k[ مقایسه میکنیم. اگه بیشتر بود، مقدار جدید رو ثبت میکنیم.
چون به ازای محاسبه هر عنصر آرایه a, مقدار o)1( زمان صرف میشه، در کل به ازای n بار اجرای الگوریتم، پیچیدیگی میشه n

Sent from my SM-T210R using Tapatalk

---

Sent from my SM-T210R using Tapatalk