T(n)=T(3n/4)+T(n^(1-b))+cnb where b and c are constants and 0 < b < 1.
(۲۵ اردیبهشت ۱۳۹۳ ۰۴:۲۱ ب.ظ)raminmz نوشته شده توسط: T(n)=T(3n/4)+T(n^(1-b))+cnb where b and c are constants and 0 < b < 1.مرتبه‌ی زمانی این سوال رو میخواستید؟ اگر اینطوره راه زیر رو بخوانید:
این رو با درخت بازگشت هم میشه حل کرد.
اما یه راه حل سریع اینه که یه عدد به b بدید. مثلاً [tex]\frac{1}{2}[/tex]. حالا رابطه تبدیل میشه به [tex]T(n)=T(\frac{3}{4}n) T(\sqrt{n}) kn[/tex] که در این رابطه k یک ثابت دلخواه هست.
حالا به استفاده از قضیه‌ی اصلی میشه مسئله رو حل کرد. جواب میشه [tex]T(n)=O(n)[/tex] چون میشه در این شرایط از رادیکال چشم‌پوشی کرد.