سلام دوستان ، کسی میدونه قضیه این بزرگترین زیر آرایه چیه؟؟ مدرسان برای جواب سوال ۴۲ کامپیوتر ۹۲ گفته از ایده بزرگترین زیر آرایه استفاده می کنیم که جواب میشه از O(n) ، که گزینه ۳ هست پارسه هم کلید این سوالو گزینه ۳ گفته ولی چیزی که تو جواب گفته گزینه یک میشه !!!
[
attachment=14382]
![[تصویر: 233555_typu5a4e.jpg]](http://dl.dropboxusercontent.com/s/wc6sw74ys6vmll4/233555_typu5a4e.jpg)
این مرتبه مربوط به روش تقسیم وحله. حالا اگه از روش پویا استفاده کنیم، و حالات رو ذخیره کنیم، مرتبه برابر n میشه
Sent from my SM-T210R using Tapatalk
(09 دى 1392 08:49 ب.ظ)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
![[تصویر: 233574_9aty5ypu.jpg]](http://dl.dropboxusercontent.com/s/g2bayarmix31y4y/233574_9aty5ypu.jpg)
![[تصویر: 233574_amuhevyv.jpg]](http://dl.dropboxusercontent.com/s/bfafbpz4g8g3md1/233574_amuhevyv.jpg)
![[تصویر: 233574_gumy2are.jpg]](http://dl.dropboxusercontent.com/s/ufymrie87a7u8t4/233574_gumy2are.jpg)
Sent from my SM-T210R using Tapatalk