با سلام
حل این رابطه بازگشتی رو میخواستم (با درخت بازگشتی)
لطفا راهنمای کنید با تشکر
۲T(n/2)+8/9T(3n/4)+n^2/log n
(۰۵ مهر ۱۳۹۵ ۱۱:۰۶ ب.ظ)Alirezaj نوشته شده توسط: با سلامسلام.
حل این رابطه بازگشتی رو میخواستم (با درخت بازگشتی)
لطفا راهنمای کنید با تشکر
۲T(n/2)+8/9T(3n/4)+n^2/log n
میشه با یکی دو تا تغییر متغیر و اینا به صورت عبارت ناهمگن در آوردش به گمونم.
با درخت خیلی چیز وحشتناکی میشه. همون توی سطح ۱ هم یه بار هم بخوایم بازش کنیم و هزینه ش رو بنویسیم نمیشه به نتیجه ای رسید.
هر رابطه ای رو میبینیم چه روشی براش بهتر هست اون رو میریم. جای خاصی با درخت رفته؟
اگه بخواید با روش تغییر متغیر حلش میکنم.
سلام
بله .لطفا حلش کنید .ممنون
من اومدم از حد گرفتن و رسیدن به قضیه اصلی برم نشد. جاگذاری هم چون دو تا تابع هست سخته. با تغییر متغیر هم به ناهمگن خیلی پیچیده میشه. درختشم که نمیشه. سختههه و اصلا این طور مسائل رو ندیدم که با درخت حل کنن چون ضریبش غیر صحیح هست یه تابع.
خلاصه تنها راهی که میمونه قضیه ی بمب اتم هست که توی کتاب پوران توضیح دادن دکتر یوسفی
قضیه ی بمب اتم: رابطه ی بازگشتی [tex]T(n)=\Sigma_{i=1}^ka_iT(\frac{n}{b_i})+f(n)[/tex] که k عدد ثابت، [tex]a_{i\: }>0[/tex] ثابت و [tex]b_{i\: }>0[/tex] برای هر i ثابت هستند مفروض است. مرتبه ی این رابطه ی بازگشتی از فرمول زیر به دست می آید:
[tex]T(n)=\theta(n^p(1+\int_1^n\frac{f(x)}{x^{p+1}}\: dx))[/tex]
که p جواب منحصر به فرد معادله ی [tex]\Sigma_{i=1}^k(\frac{a_i}{b^p_i})=1[/tex] است.
خب توی این جا داریم:
[tex]a_1=2\: \: ,\: \: a_2=\frac{8}{9}[/tex] و
[tex]b_1=2\: \: ,\: \: b_2=\frac{4}{3}[/tex]
واسه پیدا کردن p طبق فرمول میریم، میشه : [tex]\frac{a_1}{b^p_1}+\frac{a_2}{b_2^p}=\frac{\: 2}{2^p}+\frac{(\frac{8}{9})}{(\frac{4}{3})^p}=1[/tex] که باید p رو از این رابطه در بیاریم. رابطه رو ساده تر می کنیم:
[tex]\frac{\: 2}{2^p}+\frac{(\frac{8}{9})}{(\frac{4}{3})^p}=(\frac{1}{2^{p-1}})+(\frac{2^3}{9}\cdot(\frac{3^p}{4^p}))=1[/tex] که باید اینو حلش کنیم.
اما چون حلش سخته عددگذاری میکنیم جای p. به ازای p=2 معادله ی بالا میشه برابر با ۱.
خب حالا طبق فرمولی که توی قضیه گفتیم :
[tex]T(n)=\: \theta(n^2(1+\int_1^n\frac{f(x)}{x^{p+1}}))=\theta(n^2(1+\int\frac{x^2}{\log x\times x^3}dx))[/tex]
واسه گرفتن انتگرال
می دونیم که [tex]f(u)'=u'\times f'(u)[/tex] توی اینجا [tex]u=\log x\: \: ،\: \: f(x)=\log x[/tex] و [tex]f(u)'=(\log(u))'=u'\times\log u=(\log x)'\times(\log(\log x))'=\frac{1}{xlog_2^2}\times\frac{1}{\log x\times\log_2^2}=\frac{1}{x}\times\frac{1}{\log x}[/tex]
در نهایت میشه :
[tex]T(n)=\: \theta(n^2(1+\int_1^n\frac{f(x)}{x^{p+1}}))=\theta(n^2(1+\int\frac{x^2}{\log x\times x^3}dx))=\theta(n^2(1+\log\log n))[/tex]
[tex]T(n)=\theta(n^2\log\log n)[/tex]
(۰۵ مهر ۱۳۹۵ ۱۱:۰۶ ب.ظ)Alirezaj نوشته شده توسط: با سلامسلام.با قضیه Akra-Bazzi (فک کنم بمب اتم هم بهش میگن) میشه این سوال رو حل کرد.(در پاسخ بالا هم در مورد این قضیه توضیح دادن)
حل این رابطه بازگشتی رو میخواستم (با درخت بازگشتی)
لطفا راهنمای کنید با تشکر
۲T(n/2)+8/9T(3n/4)+n^2/log n
اگر شکل کلی یک رابطه بازگشتی بصورت زیر باشه:
[tex]T(n)=\: \sum_{i=1}^ka_i\: T(\frac{n}{b_i})\: +f(n)[/tex]
k: یک عدد ثابت
[tex]a_i[/tex] و [tex]b_i[/tex] اعداد ثابت بزرگتر از صفر
f(n) از بالا و پایین به توابع چند جمله ای محدود میشه. [tex]n^c\: \le\: f(n)\: \: \le\: n^d\: \: ,\: c\succ0[/tex]
حال طبق قضیه Akra-Bazi(بمب اتم) در مورد مرتبه زمانی T(n) داریم:
[tex]T(n)\: \in\theta(n^p(1+\int_1^n\frac{f(x)}{x^{p+1}}dx))\: [/tex]
که p رو میشه از رابطه زیر بدست آورد:[tex]\sum_{i=1}^k\frac{a_i}{b_i^p}\: =\: 1[/tex]
---------------------------------------------------------
حل این سوال:
ابتدا p رو محاسبه میکنیم:
[tex]\frac{2}{2^p}\: +\frac{\frac{\: 8}{9}}{(\frac{4}{3})^p}\: =1\: \: \Longrightarrow\: \: p=2[/tex]
سپس مرتبه زمانی T(n) رو محاسبه میکنیم:
[tex]T(n)\: \in\: \theta(\: n^2(1+\int_1^n\frac{\frac{x^2}{\log x}}{x^{2+1}}\: dx)\: )[/tex]
[tex]T(n)\: \in\: \theta(\: n^2(1+\int_1^n\frac{\frac{x^2}{\log x}}{x^3}\: dx)\: )[/tex]
[tex]T(n)\: \in\: \theta(\: n^2(1+\int_1^n\frac{\frac{1}{\log x}}{x^1}\: dx)\: )[/tex]
[tex]T(n)\: \in\: \theta(\: n^2(1+\int_1^n\frac{1}{x\: \log x}\: dx)\: )[/tex]
[tex]T(n)\: \in\: \theta(\: n^2(1+\log\log n)\: )[/tex]
[tex]T(n)\: \in\: \theta(\: n^2+n^2\log\log n\: )[/tex]
[tex]T(n)\: \in\: \theta(n^2\log\log n\: )[/tex]
پس جواب مسئله [tex]\: \theta(n^2\log\log n\: )[/tex] میشه.[tex]T(n)\: \in\: \theta(\: n^2(1+\int_1^n\frac{\frac{x^2}{\log x}}{x^3}\: dx)\: )[/tex]
[tex]T(n)\: \in\: \theta(\: n^2(1+\int_1^n\frac{\frac{1}{\log x}}{x^1}\: dx)\: )[/tex]
[tex]T(n)\: \in\: \theta(\: n^2(1+\int_1^n\frac{1}{x\: \log x}\: dx)\: )[/tex]
[tex]T(n)\: \in\: \theta(\: n^2(1+\log\log n)\: )[/tex]
[tex]T(n)\: \in\: \theta(\: n^2+n^2\log\log n\: )[/tex]
[tex]T(n)\: \in\: \theta(n^2\log\log n\: )[/tex]
--------------------------------------------
توضیحات:
جهت حل انتگرال [tex]\: \int\frac{1}{x\: \ln x}\: dx[/tex] میتونیم از تغییر متغیر استفاده کنیم.
[tex]u=\ln x[/tex]
[tex]du\: =\frac{\: 1}{x}\: dx[/tex]
پس با تغییر متغیر،انتگرال ما به انتگرال [tex]\int\frac{1}{u}du[/tex] تبدیل میشه که جوابش [tex]\ln\: u[/tex] میشه.
و چونکه u رو برابر [tex]\ln\: x[/tex] قرار داده بودیم،پس جواب نهایی انتگرال برابر [tex]\ln\: (\ln\: x)[/tex] میشه.
متشکرم
بخاطر هر دو جواب ممنون و سپاسگزارم.
ولی مولف محترم این جواب رو برای این رابطه آوردن!
T(n)=θ(n^2/loglogn)
(۰۶ مهر ۱۳۹۵ ۱۱:۵۱ ب.ظ)Alirezaj نوشته شده توسط: متشکرمخواهش میکنم.
بخاطر هر دو جواب ممنون و سپاسگزارم.
ولی مولف محترم این جواب رو برای این رابطه آوردن!
T(n)=θ(n^2/loglogn)
همین درسته جوابش. ایشون اشتباه کردن.
کدوم کتاب هست؟
بله متوجه شدم. سپاس فراوان
مهم نیست.ممنون
(۰۷ مهر ۱۳۹۵ ۱۲:۰۳ ق.ظ)Alirezaj نوشته شده توسط: بله متوجه شدم. سپاس فراواناز کدوم کتابه؟ ممکنه بفرمایید؟
از این جور اشتباهات توی هر کتابی هست .مهم نیست
(۰۷ مهر ۱۳۹۵ ۱۲:۱۴ ق.ظ)Alirezaj نوشته شده توسط: از این جور اشتباهات توی هر کتابی هست .مهم نیستصرفاََ واسه این پرسیدم که سوال خوبی بود.
توی نارنجی و ۶۰۰مساله و پوران پیداش نکردم.
اوکی. آره خب پیش میاد. شایدم مشکل تایپی بوده.
(۰۶ مهر ۱۳۹۵ ۱۱:۵۹ ب.ظ)Pure Liveliness نوشته شده توسط: کدوم کتاب هست؟فک کنم سوالشون از فصل اول کتاب طراحی الگوریتم مدرسان(دکتر جواد ظهیری) باشه. اونجا جواب رو با قضیه Akra-Bazzi (بمب اتم) حل کرده و جوابشو [tex]\frac{n^2}{\log\: \log n}[/tex] بدست آورده که مثل اینکه انتگرالشو اشتباه حساب کرده(چونکه مراحل حل انتگرال رو ننوشته،فقط جواب نهایی رو نوشته)
(۰۷ مهر ۱۳۹۵ ۰۱:۰۹ ق.ظ)Iranian Wizard نوشته شده توسط: فک کنم سوالشون از فصل اول کتاب طراحی الگوریتم مدرسان(دکتر جواد ظهیری) باشه. اونجا جواب رو با قضیه Akra-Bazzi (بمب اتم) حل کرده و جوابشو [tex]\frac{n^2}{\log\: \log n}[/tex] بدست آورده که مثل اینکه انتگرالشو اشتباه حساب کرده(چونکه مراحل حل انتگرال رو ننوشته،فقط جواب نهایی رو نوشته)آهان. مرسی.