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

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

ارسال:
۱۸ مهر ۱۳۹۰, ۰۴:۲۶ ب.ظ
مرتبه این تابع بازگشتی از چه راهی بدست میاید
سلام کسی میدونه مرتبه این تابع چه جوری بدست می‌اید
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


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۷۸۸ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  کمک در باره این تروجان Ghasemiyeh ۲ ۳,۰۰۷ ۲۵ آذر ۱۴۰۰ ۰۳:۰۰ ق.ظ
آخرین ارسال: one hacker alone
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۵۲ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۳۱۷ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  چگونه این خطا را موقع اجرای sql server 2014 رفع کنم ؟ farahnaz ۲ ۳,۰۱۵ ۱۹ مهر ۱۳۹۹ ۰۲:۱۸ ق.ظ
آخرین ارسال: farahnaz
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۲,۸۲۶ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  تابع مولد ss311 ۰ ۱,۴۷۸ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۴۹ ب.ظ
آخرین ارسال: ss311
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۳۶۴ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۳,۶۱۵ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t
Shocked کامپیوتر یا هنر، مسئله این است arian_61 ۲ ۴,۵۷۴ ۲۵ دى ۱۳۹۸ ۱۱:۳۱ ق.ظ
آخرین ارسال: packationmachinery

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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