زمان کنونی: ۲۹ خرداد ۱۳۹۸, ۱۱:۱۹ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مرتبه این تابع بازگشتی از چه راهی بدست میاید

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

یک روز نسیم خوش خبر می آید
بس مژده به هر کوی و گذر می آید
عطر گل عشق در فضا می پیچد
می آیی و انتظار سر می آید
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۸ مهر ۱۳۹۰, ۰۴:۵۴ ب.ظ
RE: مرتبه این تابع بازگشتی از چه راهی بدست میاید
(۱۸ مهر ۱۳۹۰ ۰۴:۲۶ ب.ظ)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]

درست بود؟
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: ahmadi_development
ارسال:
۱۸ مهر ۱۳۹۰, ۰۵:۲۲ ب.ظ (آخرین ویرایش در این ارسال: ۱۸ مهر ۱۳۹۰ ۱۱:۴۷ ب.ظ، توسط - rasool -.)
مرتبه این تابع بازگشتی از چه راهی بدست میاید
از راه درختی حل می شه.

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

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


Live in such a way that those who know you but
don't know God will come to know God because they know you

یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: ahmadi_development
ارسال:
۱۸ مهر ۱۳۹۰, ۰۶:۱۴ ب.ظ
RE: مرتبه این تابع بازگشتی از چه راهی بدست میاید
ممنون
جواب اخر درسته ا
در مورد سوال دوم کسی نظری نداره

یک روز نسیم خوش خبر می آید
بس مژده به هر کوی و گذر می آید
عطر گل عشق در فضا می پیچد
می آیی و انتظار سر می آید
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۸ مهر ۱۳۹۰, ۰۶:۲۳ ب.ظ
مرتبه این تابع بازگشتی از چه راهی بدست میاید
از این حقیر در مورد سوال دوم:

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

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


Live in such a way that those who know you but
don't know God will come to know God because they know you

یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۸ مهر ۱۳۹۰, ۰۶:۳۷ ب.ظ (آخرین ویرایش در این ارسال: ۱۸ مهر ۱۳۹۰ ۰۷:۲۰ ب.ظ، توسط sasanlive.)
RE: مرتبه این تابع بازگشتی از چه راهی بدست میاید
(۱۸ مهر ۱۳۹۰ ۰۶:۱۴ ب.ظ)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.

پــرواز را به خاطـر بسپـار پـرنده مردنـی اسـت.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: marzieh


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Star دوره موضوعی --> حل روابط بازگشتی --> روابط دهم - rasool - ۲ ۲,۰۷۶ ۰۳ بهمن ۱۳۹۳ ۱۲:۴۵ ق.ظ
آخرین ارسال: mostafa2012
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه ششم - rasool - ۸ ۳,۵۰۸ ۰۱ آبان ۱۳۹۲ ۱۰:۰۷ ق.ظ
آخرین ارسال: Mänu
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه نهم - rasool - ۵ ۲,۵۴۱ ۱۳ مهر ۱۳۹۲ ۰۳:۲۵ ب.ظ
آخرین ارسال: vojoudi
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه هفتم - rasool - ۱ ۱,۹۰۸ ۱۱ بهمن ۱۳۹۰ ۰۴:۰۶ ب.ظ
آخرین ارسال: Aurora
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه سوم - rasool - ۴ ۲,۵۳۳ ۱۱ بهمن ۱۳۹۰ ۱۲:۱۹ ب.ظ
آخرین ارسال: Masoud05
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه پنجم - rasool - ۱ ۲,۰۲۴ ۱۱ بهمن ۱۳۹۰ ۱۲:۱۸ ب.ظ
آخرین ارسال: Aurora
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه هشتم - rasool - ۱ ۲,۲۱۵ ۱۰ بهمن ۱۳۹۰ ۰۹:۰۷ ب.ظ
آخرین ارسال: Mohammad-A
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه چهارم - rasool - ۱ ۱,۷۶۳ ۱۰ بهمن ۱۳۹۰ ۰۹:۰۰ ب.ظ
آخرین ارسال: Mohammad-A
Star دوره موضوعی --> حل روابط بازگشتی --> رابطه دوم - rasool - ۱ ۲,۱۷۴ ۱۰ بهمن ۱۳۹۰ ۰۲:۳۴ ب.ظ
آخرین ارسال: Mohammad-A
  یه سوال بازگشتی از قضیه اصلی پشتکار ۱۱ ۳,۹۸۵ ۰۹ آبان ۱۳۹۰ ۱۲:۱۲ ق.ظ
آخرین ارسال: sasanlive

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close