سلام
جواب این رابطه بازگشتی چی میشه؟
!T(N)=T(N/2)+LGN
چون عبارت [tex]lg(n!)[/tex] با [tex]nlgn[/tex] هم مرتبه هستش میتونید تو رابطه بازگشتی به جای [tex]lg(n!)[/tex] عبارت [tex]nlgn[/tex] رو قرار بدید و بعد با یه تغییر متغیر ساده میتونید جواب رو به دست بیارید
اول تغییر متغیر زیر رو در نظر می گیریم:
[tex]n=2^{k}\Rightarrow k=lgn[/tex]
حالا شکل معادله رو بعد از اعمال تغییر متغیر می نویسیم:[tex]T(2^{k})=T(2^{k-1}) 2^{k}k[/tex]
حالا با در نظر گرفتن [tex]S(k)=T(2^{k})[/tex] داریم:[tex]S(k)=S(k-1) 2^{k}k[/tex]
معادله بالا یک معادله بازگشتی نا همگن با ضرایب ثابت هستش که معادله مشخصه اون به صورت زیر هستش:[tex](k-2)^{2}=0[/tex]
معادله بالا ریشه مضاعف داره و اگر ریشه‌ها رو در جواب عمومی معادلات بازگشتی قرار بدیم داریم:[tex]S(k)=C_{1}2^{k} C_{2}k2^{k}[/tex]
حالا با تغییر متغیر معکوس داریم:[tex]T(n)=C_{1}n C_{2}nlgn[/tex]
پس T از مرتبه تتای nlgn هستشپ.ن: جواب رو با توجه به اون چیزهایی که از این بحث یادم می اومد نوشتم و ممکنه صد در صد درست نباشه
با تشکر از آقای mfXpert
همچنین
پاسخ رابطه‌ی: [tex]\large T(n)=T(\frac{n}{2}) nlogn[/tex]
به سادگی از راه قضیه اصلی حل می شه و جواب [tex]\large \theta (nlogn)[/tex]
خواهد بود.
(۱۸ مهر ۱۳۹۰ ۰۴:۴۱ ب.ظ)livane_abi نوشته شده توسط:(18 مهر ۱۳۹۰ ۰۴:۲۸ ب.ظ)mfXpert نوشته شده توسط: اول تغییر متغیر زیر رو در نظر می گیریم:
[tex]n=2^{k}\Rightarrow k=lgn[/tex]حالا شکل معادله رو بعد از اعمال تغییر متغیر می نویسیم:
[tex]T(2^{k})=T(2^{k-1}) 2^{k}k[/tex]حالا با در نظر گرفتن [tex]S(k)=T(2^{k})[/tex] داریم:
[tex]S(k)=S(k-1) 2^{k}k[/tex]معادله بالا یک معادله بازگشتی نا همگن با ضرایب ثابت هستش که معادله مشخصه اون به صورت زیر هستش:
[tex](k-2)^{2}=0[/tex]معادله بالا ریشه مضاعف داره و اگر ریشه‌ها رو در جواب عمومی معادلات بازگشتی قرار بدیم داریم:
[tex]S(k)=C_{1}2^{k} C_{2}k2^{k}[/tex]حالا با تغییر متغیر معکوس داریم:
[tex]T(n)=C_{1}n C_{2}nlgn[/tex]پس T از مرتبه تتای nlgn هستش
پ.ن: جواب رو با توجه به اون چیزهایی که از این بحث یادم می اومد نوشتم و ممکنه صد در صد درست نباشه
با تشکر فراوان از جوابتون
ولی جواب زده [tex]\theta( N lg\, ^{^{2}} n )[/tex]
دوست عزیز به احتمال زیاد جواب رو غلط زده چراکه سوال شما هم با تغییر متغیر وهم به سادگی با قضیه اصلی حل می شه
از mfXpert هم دانشگاهی سابق خودم، هم تشکر می کنم، از جوابشون واقعا استفاده کردم
اینم راه حل قضیه اصلی:
a=1,b=2,f(n)=nlogn,k=0
قاعده۳
f(n) = Ω( n ^ (k+epsi
برقراره در نتیجه (T(N)=θ(f(n) )=θ(nlogn
با نظر ahmadi_development کاملا موافقم
طبق قضیه اصلی (T(n)=[tex]T(n)=aT(\frac{n}{b}) cf(n)[/tex]
جواب می شود n log n، اینکه livane_abi میگین جواب هست n log^2 n ،طبق قضیه اصلی جواب در صورتی این می شود که سوال ضریب ۲ داشته باشد (!T(N)=2T(N/2)+LGN )، پس یا اشتباه دیده (با احترام )و یا کتاب اشتباه زده !
(۱۸ مهر ۱۳۹۰ ۰۶:۱۷ ب.ظ)yarandish نوشته شده توسط: ،طبق قضیه اصلی جواب در صورتی این می شود که سوال ضریب ۲ داشته باشد (!T(N)=2T(N/2)+LGN )،دوست عزیز، توجه کنید که اگه ضریب ۲ داشت ،یعنی رابطه‌ی ما [tex]\large T(n)=2T(\frac{n}{2}) nlogn[/tex]
بود اونوقت با قضیه اصلی حل نمی شد. بلکه باید با راههای دیگه حل می کردیم که همانطوری که فرمودید می شه [tex]\large \theta (nlog^{2}n)[/tex]
تاپیک مرتبط:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۸ مهر ۱۳۹۰ ۰۵:۳۴ ب.ظ)ahmadi_development نوشته شده توسط:(18 مهر ۱۳۹۰ ۰۴:۴۱ ب.ظ)livane_abi نوشته شده توسط:(18 مهر ۱۳۹۰ ۰۴:۲۸ ب.ظ)mfXpert نوشته شده توسط: اول تغییر متغیر زیر رو در نظر می گیریم:
[tex]n=2^{k}\Rightarrow k=lgn[/tex]حالا شکل معادله رو بعد از اعمال تغییر متغیر می نویسیم:
[tex]T(2^{k})=T(2^{k-1}) 2^{k}k[/tex]حالا با در نظر گرفتن [tex]S(k)=T(2^{k})[/tex] داریم:
[tex]S(k)=S(k-1) 2^{k}k[/tex]معادله بالا یک معادله بازگشتی نا همگن با ضرایب ثابت هستش که معادله مشخصه اون به صورت زیر هستش:
[tex](k-2)^{2}=0[/tex]معادله بالا ریشه مضاعف داره و اگر ریشه‌ها رو در جواب عمومی معادلات بازگشتی قرار بدیم داریم:
[tex]S(k)=C_{1}2^{k} C_{2}k2^{k}[/tex]حالا با تغییر متغیر معکوس داریم:
[tex]T(n)=C_{1}n C_{2}nlgn[/tex]پس T از مرتبه تتای nlgn هستش
پ.ن: جواب رو با توجه به اون چیزهایی که از این بحث یادم می اومد نوشتم و ممکنه صد در صد درست نباشه
با تشکر فراوان از جوابتون
ولی جواب زده [tex]\theta( N lg\, ^{^{2}} n )[/tex]
دوست عزیز به احتمال زیاد جواب رو غلط زده چراکه سوال شما هم با تغییر متغیر وهم به سادگی با قضیه اصلی حل می شه
از mfXpert هم دانشگاهی سابق خودم، هم تشکر می کنم، از جوابشون واقعا استفاده کردم
اینم راه حل قضیه اصلی:
a=1,b=2,f(n)=nlogn,k=0
قاعده۳
f(n) = Ω( n ^ (k+epsi
برقراره در نتیجه (T(N)=θ(f(n) )=θ(nlogn
سلام
اینجا که k=1هست درnlogn!!!!چرا شما k=0گرفتید.بعضیها فرمودند حل نمیشه و بعضیها هم گفتن حل میشه ولی من اینجور سوالاتو چه کتاب پوران و چه کتاب پارسه دیدم با قضیه اصلی حل کردن وnlog nرو هم همیشه k=1قرار دادن!!!!!!!!!!!!!!الان دیگه به همه چیز شک کردم و موندم چی درسته!!!!!!!!!!!!!باید فکر اساسی کنم.
۱ی به داد برسه با دلیل محکم.
(۱۸ مهر ۱۳۹۰ ۱۰:۱۷ ب.ظ)khavar_1365 نوشته شده توسط: [quote='ahmadi_development' pid='49095' dateline='1318251869']اولین سوال در اولین ارسال به روش اصلی حل میشه.
[quote='livane_abi' pid='49082' dateline='1318248692']
[quote='mfXpert' pid='49078' dateline='1318247905']
سلام
اینجا که k=1هست درnlogn!!!!چرا شما k=0گرفتید.بعضیها فرمودند حل نمیشه و بعضیها هم گفتن حل میشه ولی من اینجور سوالاتو چه کتاب پوران و چه کتاب پارسه دیدم با قضیه اصلی حل کردن وnlog nرو هم همیشه k=1قرار دادن!!!!!!!!!!!!!!الان دیگه به همه چیز شک کردم و موندم چی درسته!!!!!!!!!!!!!باید فکر اساسی کنم.
۱ی به داد برسه با دلیل محکم.
ولی آخری[tex]f(n)=2T(\frac{n}{2}) nlogn[/tex] حل نمیشه.
در مورد سوالتون:
[tex]log1=0[/tex] لگاریتم ۱ در مبنای ۲ مساوی ۰ میشه.پس [tex]n^{k}=n^{0}=1[/tex].
پس [tex]1=o(nlogn)[/tex].
جمع بندی:
در این تاپیک در مورد دو رابطه بحث شد:
اولین رابطه:
[tex]\large T(n)=T(\frac{n}{2}) nlogn[/tex]
** با قضیه اصلی حل می شود .
** پاسخی رو هم آقای mfXpert در پست چهارم داده اند (از راه تغییر متغیر)
**پاسخ آن [tex]\large O(nlogn)[/tex] می شود.
---------------------------------------------------------------------------------
دومین رابطه:
[tex]\large T(n)=2T(\frac{n}{2}) nlogn[/tex]
** با قضیه اصلی حل نمی شود. (ولی می توان با تبصره و تعمیمی که در این مورد وجود دارد آن را حل کرد)
** می توان از راه درختی آن را حل کرد.
** پاسخ آن [tex]\large O(nlog^{2}n)[/tex] می شود.
(۱۸ مهر ۱۳۹۰ ۰۲:۲۸ ب.ظ)livane_abi نوشته شده توسط: سلام
جواب این رابطه بازگشتی چی میشه؟
!T(N)=T(N/2)+LGN
فکر کنم اینجوری میشه:
[attachment=1384]
دوستان برای تشکر هم از دکمه تشکر و یا تایید ارسال استفاده کنن( بجای گزاشتن یک ارسال ). با اجازتون ارسال های حاشیه ای رو حذف میکنم تا دوستانی که بعدا از این موضوع استفاده میکنن، مستقیم به اصل موضوع رجوع کنند.
با استفاده از تبصره ای که آقای یوسفی در پوران گفتن میشه گفت که
[tex]T(n)=\bigcirc (n* lgn * lgn)[/tex]
اگه از روش درخت بازگشتی هم این مسئله رو حل کنیم
[tex]nlgn \frac{n}{2}lg\frac{n}{2} \frac{n}{4}lg\frac{n}{4} ... 0 = n(lgn \frac{1}{2}lg\frac{n}{2} \frac{1}{4}lg\frac{n}{4} ... 0)[/tex]
که تعداد جملات داخل پرانتز lgn تاست و خود جملات داخل پرانتز هم از مرتبه lgn است
که میشه
[tex]O(n*lgn*lgn)[/tex]
(۱۹ مهر ۱۳۹۰ ۰۱:۳۲ ق.ظ)ahmadnouri نوشته شده توسط: با استفاده از تبصره ای که آقای یوسفی در پوران گفتن میشه گفت کهدر ارسال های قبلی ،دوستان این مسئله رو با ۳ روش حل کردند:
[tex]T(n)=\bigcirc (n* lgn * lgn)[/tex]
اگه از روش درخت بازگشتی هم این مسئله رو حل کنیم
[tex]nlgn \frac{n}{2}lg\frac{n}{2} \frac{n}{4}lg\frac{n}{4} ... 0 = n(lgn \frac{1}{2}lg\frac{n}{2} \frac{1}{4}lg\frac{n}{4} ... 0)[/tex]
که تعداد جملات داخل پرانتز lgn تاست و خود جملات داخل پرانتز هم از مرتبه lgn است
که میشه
[tex]O(n*lgn*lgn)[/tex]
۱- تغییر متغیر( توسط دوست خوبم mfXpert )
۲- روش اصلی( Master )
۳- روش جایگذاری .