تالار گفتمان مانشت

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

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

سلام نمی دونم درسته یا نه ولی انگار این همون سوال منه !
یه راهی پیدا کردم

ممکنه درس نباشه ولی من گاهی از این روش درختیاا اینو حل می کنم

حالا اینا همینجوری هست تا میرسه به [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]

درست بود؟

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

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

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

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

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

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

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

(18 مهر 1390 06:14 ب.ظ)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) رو گرفته .