تالار گفتمان مانشت
مرتبه این تابع بازگشتی از چه راهی بدست میاید - نسخه‌ی قابل چاپ

مرتبه این تابع بازگشتی از چه راهی بدست میاید - ahmadi_development - 18 مهر ۱۳۹۰ ۰۴:۲۶ ب.ظ

سلام کسی میدونه مرتبه این تابع چه جوری بدست می‌اید
t(n)=2t(n/2)+nlogn
این مثال کتاب دکتر قدسی (صفحه ۱۰۵) که گفته از راه قضیه اصلی بدست نمی‌اید وباید از راه دیگری خل شود اول اینکه دوستان اگه راه حلی به غیر از روش استقرا دارن لطف کنن جواب بدن
ثانیا کسی می تونه این جمله رو تفسیر کنه
شرایط استفاده از قضیه اصلی:بزرگ یا کوچک بودن اهنگ رشد دو تابع یعنی f(n), g(n)
باید چند جمله ای باشد مثلا اهنگ رشد n^2 از nlogn ویا n از logn به صورت چند جمله ای بیشتر است ولی اهنگ رشد nlogn از n به صورت چند جمله ای بیشتر نیست

RE: مرتبه این تابع بازگشتی از چه راهی بدست میاید - livane_abi - 18 مهر ۱۳۹۰ ۰۴:۵۴ ب.ظ

(۱۸ مهر ۱۳۹۰ ۰۴:۲۶ ب.ظ)ahmadi_development نوشته شده توسط:  سلام کسی میدونه مرتبه این تابع چه جوری بدست می‌اید
t(n)=2t(n/2)+nlogn
این مثال کتاب دکتر قدسی (صفحه ۱۰۵) که گفته از راه قضیه اصلی بدست نمی‌اید وباید از راه دیگری خل شود اول اینکه دوستان اگه راه حلی به غیر از روش استقرا دارن لطف کنن جواب بدن
ثانیا کسی می تونه این جمله رو تفسیر کنه
شرایط استفاده از قضیه اصلی:بزرگ یا کوچک بودن اهنگ رشد دو تابع یعنی f(n), g(n)
باید چند جمله ای باشد مثلا اهنگ رشد n^2 از nlogn ویا n از logn به صورت چند جمله ای بیشتر است ولی اهنگ رشد nlogn از n به صورت چند جمله ای بیشتر نیست

سلام نمی دونم درسته یا نه ولی انگار این همون سوال منه !
یه راهی پیدا کردم
Big Grin
ممکنه درس نباشه ولی من گاهی از این روش درختیاا اینو حل می کنم
nlog n

n/2 log n/2*******n/2log n/2
حالا اینا همینجوری هست تا میرسه به [tex]\frac{n}{2^{_{k}}}[/tex]
که k باید logn باشه
یعنی
nlogn + nlogn/2 + nlogn/4 +...+ n log n/n^{logn}}
که میشه
(n(logn +logn+logn+...+logn
چون تعداد log n تاس میشه [tex]n log{_{}}^{2}n[/tex]

درست بود؟

مرتبه این تابع بازگشتی از چه راهی بدست میاید - - rasool - - 18 مهر ۱۳۹۰ ۰۵:۲۲ ب.ظ

از راه درختی حل می شه.

جمع هزینه های درخت (پس از ساده سازی) می شه:

[tex]\large n((logn logn-1 logn-2 logn-3 ... 1))=\frac{n(logn)(logn-1)}{2}=O(nlog^{2}n)[/tex]

RE: مرتبه این تابع بازگشتی از چه راهی بدست میاید - ahmadi_development - 18 مهر ۱۳۹۰ ۰۶:۱۴ ب.ظ

ممنون
جواب اخر درسته ا
در مورد سوال دوم کسی نظری نداره

مرتبه این تابع بازگشتی از چه راهی بدست میاید - - rasool - - 18 مهر ۱۳۹۰ ۰۶:۲۳ ب.ظ

از این حقیر در مورد سوال دوم:

ابتدا فرمول قضیه اصلی رو خوب نگاه کنید.
در اونجاهایی که اپسیلن رو بعلاوه یا منها کرده دقت کنید.

در مورد دو مثال( یکی که قضیه اصلی براش جواب می ده و یکی دیگه که قضیه اصلی براش جواب نمی ده )فرمول رو امتحان کنید( در مورد اون اپسیلن‌ها خوب دقت کنید ). فکرمی کنم متوجه بشوید.

RE: مرتبه این تابع بازگشتی از چه راهی بدست میاید - sasanlive - 18 مهر ۱۳۹۰ ۰۶:۳۷ ب.ظ

(۱۸ مهر ۱۳۹۰ ۰۶:۱۴ ب.ظ)ahmadi_development نوشته شده توسط:  ممنون
جواب اخر درسته ا
در مورد سوال دوم کسی نظری نداره

[tex]\frac{nlogn}{n}=logn[/tex]

[tex]0<\epsilon <1[/tex] , [tex]logn=o(n^{\epsilon })[/tex]

o در دومین فرمول اوی کوچیکه. یعنی اگر اپسیلون بین ۰ و ۱ باشه آهنگ رشد logn همیشه بصورت چند جمله ای کوچکتر از [tex]n^{\epsilon }[/tex] میباشد.
اهنگ رشد logn یه چیزایی تو مایه های آهنگ رپه, نمیشه آهنگ پاپ حسابش کرد واسه همین زیاد تحویلش نمی گیرن. تو دلت به حالش نسوزه, حقشه نامرد جلوی رشد بچه(n) رو گرفته Big GrinTongue.