(۲۷ دى ۱۳۹۵ ۰۴:۰۵ ب.ظ)shamim1395 نوشته شده توسط:  پیچیدگی زمانی تعداد جمع ها و تفریق ها برای الگوریتم استراسن به صورت
[tex]T(n)=7t(\frac{n}{2})+18(\frac{n}{2})^2\: \: \: \: \: \: \: \: ,\: \: \: \: \: \: \: \: \: \: \: T(1)=1[/tex]

چگونه به حل زیر می رسد؟


[tex]T(n)=6n^{\log^72}-6n^2\: \: \: \: ,\: \: \: \: \: \: \: \: \: [/tex]

برای اینکه به طور دقیق (با ضرایب) مرتبه‌ی الگوریتم رو پیدا کرد میشه از روش Akra-Bazzi استفاده کرد.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

در اینجا [tex]\frac{7}{2^p}=1\: \longrightarrow\: 2^p=7\: \longrightarrow\: p=\log_2^7[/tex]

بنابراین [tex]T(n)=\theta(n^{\log_2^7}(1+\int_1^n\frac{18(\frac{x}{2})^2}{x^{\log_2^7+1}}dx))[/tex]

[tex]=n^{\log^7_2}(1+\frac{18}{4}\int_1^n\frac{1}{x^{\log_2^7-1}}dx)=n^{\log^7_2}(1+\frac{18}{4}(\frac{-1}{\log_2^7-2}x^{2-\log_2^7})|_1^n)=n^{\log_2^7}(1-\frac{18n^{2-\log^7_2}}{4(\log_2^7-2)}+\frac{18}{4(\log_2^7-2)})=6.6n^{\log^7_2}-6.6n^2[/tex]