سلام بچه ها رابطه بازگشتی مگر گزینه ۲ نمیشد چرا سنجش گفت ۳؟
طبق این قضیه
این قضیه درست میدانم الان logaدر پایه b میشد صفر پس باید تتا خود fبشد
(۰۹ اردیبهشت ۱۳۹۵ ۱۰:۵۱ ق.ظ)mahsa72 نوشته شده توسط: این قضیه درست میدانم الان logaدر پایه b میشد صفر پس باید تتا خود fبشد
n به توان ۰ میشه ۱ حالا یک رو بزارین پشت لگاریتم حله.
ن دیگ این ک قضیه نمیشد که این در صورتی که f وبا nب توان logاز یک تتا باشند این حالت ۳هست از امگا است
نه این از مدل حالت اصلی مستر قابل حل نیست
یه مدل تعمیم یافته مستر هست که می گه اگه رابطه بازگشتی به صورت [tex]T(n)=aT(\frac{n}{b}) \log^kn\: \ast f(n)[/tex] باشد
اگر [tex]n^{\log_b^a}[/tex] و [tex]f(n)[/tex] هم مرتبه باشند آن گاه [tex]T(n)=O(f(n)\ast\log^{k 1}n)[/tex]
در این سوال ، هم f(n) و هم [tex]n^{\log_b^a}[/tex] برایر یک هستند پس [tex]T(n)=O(\log^3n)[/tex] است.
(۱۰ اردیبهشت ۱۳۹۵ ۰۶:۵۱ ق.ظ)fatemeh69 نوشته شده توسط: نه این از مدل حالت اصلی مستر قابل حل نیست
یه مدل تعمیم یافته مستر هست که می گه اگه رابطه بازگشتی به صورت [tex]T(n)=aT(\frac{n}{b}) \log^kn\: \ast f(n)[/tex] باشد
اگر [tex]n^{\log_b^a}[/tex] و [tex]f(n)[/tex] هم مرتبه باشند آن گاه [tex]T(n)=O(f(n)\ast\log^{k 1}n)[/tex]
در این سوال ، هم f(n) و هم [tex]n^{\log_b^a}[/tex] برایر یک هستند پس [tex]T(n)=O(\log^3n)[/tex] است.
منم همین رو میگفتم ولی نه مثل توضیح کامل شما.
الان کجا Fبا این log هم مرتبه است ؟؟؟؟؟؟؟ما الان log1درپایه ۴ داریم مرتبه میشد یک اما مرتب fاز log n ب توان ۲خب مگ کمتر نیست؟
(۱۰ اردیبهشت ۱۳۹۵ ۰۹:۳۹ ق.ظ)mahsa72 نوشته شده توسط: الان کجا Fبا این log هم مرتبه است ؟؟؟؟؟؟؟ما الان log1درپایه ۴ داریم مرتبه میشد یک اما مرتب fاز log n ب توان ۲خب مگ کمتر نیست؟
تو این قضیه نباید مقایسه ای انجام بدین و اگر شرایط قضیه برقرار شد(که بر قراره) با توجه به قضیه جواب بدست میاد.
اگر رابطه داده شده در صورت سوال را به فرم [tex]T(n)=aT(\frac{n}{b}) \log^kn\: \ast f(n)[/tex]
در نظر بگیریم در این صورت a=1 , b=4 , f(n)=1 است
که[tex]n^{\log_b^a}=n^{\log_4^1}=n^0=1[/tex] است که با f(n)=1 هم مرتبه استو. دقت کنید که f(n) را ۱ در نظر می گیریم و اون لگاریتم به توان دو رو ضریب لگاریتمی f(n) محسوب می کنیم
و قضیه ای که براتون نوشتم می گه هر وقت [tex]n^{\log_b^a}[/tex] با f(n) بابر بود رابطه میشه از مرتبه ی f(N) ضرب در لگاریتم به توان یکی بیشتر