پوران جوابشو با برنامه نویسی پویا داده
پارسه با روش حریصانه
با ذکر دلیل هرکسی جوابشو میدونه، ممنون میشم.
به نظرم ۱ غلطه
--
در مورد ۳ چیزی نمی دونم ولی فکر می کنم مربوط به این بحث نیست.
----
تا اونجا که من می دونم روش پویا از روش تقسیم و غلبه بهتر و بهینه تره.(مثلا برای فیبوناثی داریم: روش تقسیم = ۲ به توان n/2 ولی روش پویا میشه order_n )
---
پس فکر کنم گزینه ی ۴ هم رد میشه و گزینه ی ۲ باید درست باشه
-------------------
اینم تحلیل من با یک مثال :
![[تصویر: PUYA.gif]](https://img.manesht.ir/PUYA.gif)
منم با نظر دوستمون موافقم!
کلا مسائل بهینه سازی از روش پویا به جواب بهتری می رسند.
نقل از پارسه:
با روش حریصانه با مرتبه (O(nlogn قابل حل است.
(۲۵ دى ۱۳۹۱ ۰۲:۲۹ ق.ظ)adel28 نوشته شده توسط: با روش حریصانه با مرتبه (O(nlogn قابل حل است.نظرم عوض شده!به نظر منم حریصانه با توجه با الگوریتم انتخاب فعالیت ها بهتره!دقیقا خود زمانبندی فعالیت های بدون مهلته!
این جوابی ست که استاد الگوریتممون داده است. در فایل پیوست با شکل سعی کرده ام توضیح اش بدهم امیدوارم مفید باشد
موید باشید
[attachment=9088]
با تمام روشهای برنامه نویسی میشه براش الگوریتم با زمان چند جمله ای نوشت. به نظر من این تست مشکل داره و بحث درباره اش بی فایدست!
این الگوریتم رو میشه در زمان چندجمله‌ای با روش برنامه‌ریزی پویا مشابه ضرب ماتریس‌ها (تا جایی که یادمه) حلش کرد.
مرتبه حریصانه میشه nlgn و مرتبه پویا میشه n^3
حالا سوال من از دوستان اینه که آیا میشه گفت nlgn مرتبه چند جمله ای نیست و این نکته سوال باشه؟!یعنی لگاریتمیه!
(۱۱ بهمن ۱۳۹۱ ۰۱:۰۱ ب.ظ)۸Operation نوشته شده توسط: مرتبه حریصانه میشه nlgn و مرتبه پویا میشه n^3
حالا سوال من از دوستان اینه که آیا میشه گفت nlgn مرتبه چند جمله ای نیست و این نکته سوال باشه؟!یعنی لگاریتمیه!
تابع [tex]f(n)[/tex] از مرتبه چند جمله ایست اگر [tex]log(f(n))=\Theta(logn)[/tex].
خوب حالا اگر از nlgn لگاریتم بگیریم جواب میشه [tex]log(nlgn)=logn log(lgn)[/tex] که این هم رشد است با همون [tex]\Theta(logn)[/tex].
پس nlgn از مرتبه چند جمله ایست!