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

مشکل در حل روابط بازگشتی به روش تغییر متغییر

ارسال:
  

sara27 پرسیده:

مشکل در حل روابط بازگشتی به روش تغییر متغییر

سلام ممنون میشم بگین چه جوری روابط بازگشتی رو به روش تغییر متغییر میشه حل کرد.!!؟
به عنوان نمونه ..مثال صفحه ۳۵ یوسفی چاپ بهار ۹۴
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

Pure Liveliness پاسخ داده:

RE: مشکل در حل روابط بازگشتی به روش تغییر متغییر

سلام.
چون توی بعضی از روابط بازگشتی گاهی رادیکال داریم محاسبه ش سخت هست و با روش های معمولی نمیتونیم احتمالا حلش کنیم. باید یه کاری کنیم که از شر رادیکال خلاص بشیم.
این جا برای این که رادیکال رو از بین ببریم شاید پیشنهاد بشه که رادیکال رو به صورت توان [tex]\frac{1}{2}[/tex] بنویسیم. اما خب فرقی نداره و بعدش نمیشه هیچ کاری کرد. این جا ها که رادیکال داریم میشه ۲ به توان m گرفت n رو. اگه رادیکال تودرتو بود و اینا فرق داشت قضیه.
[tex]T(n)=3T(\sqrt[3]{n})+\log n[/tex]
حالا تغییر متغیر برای خلاص شدن از رادیکال: [tex]n=2^m\: \longrightarrow\: \log n=m[/tex]
[tex]T(2^m)=3T(\sqrt[3]{2^m})+\log2^m=3T(2^{\frac{m}{3}})+m[/tex]تغییر متغیر دوم برای تبدیل به رابطه ی بازگشتی غیر توانی : [tex]T(2^m)=S(m)[/tex]
[tex]S(m)=3S(\frac{m}{3})+m[/tex] که از مرتبه ی mlogm هست و چون [tex]\log n=m[/tex] پس میشه از مرتبه ی [tex]\log n\times\log\log n[/tex]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

arash691 پاسخ داده:

RE: مشکل در حل روابط بازگشتی به روش تغییر متغییر

(۰۵ اسفند ۱۳۹۵ ۰۷:۱۵ ب.ظ)sara27 نوشته شده توسط:  سلام ممنون میشم بگین چه جوری روابط بازگشتی رو به روش تغییر متغییر میشه حل کرد.!!؟
به عنوان نمونه ..مثال صفحه ۳۵ یوسفی چاپ بهار ۹۴

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

[tex]T(n)=\: T(n^{\frac{1}{3}})+T(n^{\frac{2}{3}})+\log n[/tex]

[tex]T(n)=2T(\sqrt{n})+\frac{n}{\log n}[/tex]
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  روابط احساسی خارج از ازدواج مردان متأهل morweb ۶۲ ۳۴,۷۴۳ ۱۰ بهمن ۱۴۰۲ ۰۲:۴۱ ب.ظ
آخرین ارسال: fatemehbiglar
  رفع اشکال نصب جاوا، مشکل ساخته نشدن virtual machine shiivaa ۱۲ ۲۰,۸۷۶ ۱۹ آبان ۱۳۹۹ ۰۷:۲۹ ب.ظ
آخرین ارسال: wanted471
Sad مشکل در برنامه نویسی شیء گرا Xialu ۰ ۲,۳۰۵ ۰۵ شهریور ۱۳۹۹ ۱۲:۰۰ ب.ظ
آخرین ارسال: Xialu
  تغییر رشته برای کنکور rezap13 ۰ ۱,۸۴۹ ۰۴ شهریور ۱۳۹۹ ۱۲:۲۰ ب.ظ
آخرین ارسال: rezap13
  مشکل در حل تست ۲۲ فصل اول کتاب گسسته یوسفی pure.yaser ۷ ۹,۳۹۱ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۵۴ ب.ظ
آخرین ارسال: mohsentafresh
  تعداد روش های نوشتن عدد n ss311 ۲ ۳,۳۷۳ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  تغییر رشته از ریاضی به علوم کامپیوتر در ارشد Fghs ۳ ۵,۴۸۸ ۲۱ دى ۱۳۹۸ ۰۵:۱۱ ب.ظ
آخرین ارسال: parisa1140
  تغییر عجیب رشته های فناوری اطلاعات ارشد کنکور ۹۸ irmacfa ۴ ۶,۲۹۰ ۱۱ دى ۱۳۹۸ ۰۶:۱۴ ب.ظ
آخرین ارسال: Alireza.Moftakharzadeh
  مشاوره روش تحقیق و تحلیل آماری sirvan.t ۰ ۲,۱۷۵ ۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ
آخرین ارسال: sirvan.t
  منبع متناسب با شرایط کسانی که قصد تغییر رشته دارند MrBob ۷ ۶,۱۸۱ ۱۶ آبان ۱۳۹۸ ۱۱:۳۵ ب.ظ
آخرین ارسال: marvelous

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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