تالار گفتمان مانشت
بزرگترین زیر آرایه - نسخه‌ی قابل چاپ
بزرگترین زیر آرایه - zara-t - 09 دى ۱۳۹۲ ۰۵:۲۳ ب.ظ

سلام دوستان ، کسی میدونه قضیه این بزرگترین زیر آرایه چیه؟؟ مدرسان برای جواب سوال ۴۲ کامپیوتر ۹۲ گفته از ایده بزرگترین زیر آرایه استفاده می کنیم که جواب میشه از O(n) ، که گزینه ۳ هست پارسه هم کلید این سوالو گزینه ۳ گفته ولی چیزی که تو جواب گفته گزینه یک میشه !!!Huh
[attachment=14382]

Re: بزرگترین زیر آرایه - hoomanab - 09 دى ۱۳۹۲ ۰۸:۴۹ ب.ظ

[تصویر: 233555_typu5a4e.jpg]
این مرتبه مربوط به روش تقسیم وحله. حالا اگه از روش پویا استفاده کنیم، و حالات رو ذخیره کنیم، مرتبه برابر n میشه

Sent from my SM-T210R using Tapatalk

RE: بزرگترین زیر آرایه - zara-t - 09 دى ۱۳۹۲ ۰۹:۴۸ ب.ظ

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

Sent from my SM-T210R using Tapatalk

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

RE: بزرگترین زیر آرایه - hoomanab - 09 دى ۱۳۹۲ ۱۰:۰۶ ب.ظ

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

Sent from my SM-T210R using Tapatalk
[تصویر: 233574_9aty5ypu.jpg]
[تصویر: 233574_amuhevyv.jpg]
[تصویر: 233574_gumy2are.jpg]

Sent from my SM-T210R using Tapatalk