تالار گفتمان مانشت

مرتبه ی زمانی الگوریتم زیر رو از روش جایگذاری بدست اورده جاهایی که دورش خط کشیدم رو متوجه نمی شم از جایی که نوشته "بنابراین می توانیم رابطه را به صورت زیر در نظر بگیریم ....."

همچینن می دونم که این سوال از قضیه اصلی هم حل می شود اما از روش جایگذاری هم می خواهم بلد باشم.

سلام
اول تا اونجایی که بتونیم فرمول کلی این رابطه را حدس بزنیم معادله رو گسترش میدیم پس اینطوری میشه:

[tex]ُT(n)=8T(\frac{n}{2}) n^2[/tex]
[tex]ُT(n)=8(8T(\frac{n}{4}) (\frac{n}{2})^2) n^2=8^2T(\frac{n}{4}) 2n^2 n^2[/tex]
[tex]ُT(n)=82(8T(\frac{n}{8}) (\frac{n}{4})^2) 2n^2 n^2=8^3T(\frac{n}{8}) 2^2n^2 2n^2 n^2[/tex]
[tex]ُT(n)=8^3(8T(\frac{n}{16}) (\frac{n}{8})^2) 2^2n^2 2n^2 n^2=8^4T(\frac{n}{16}) 2^3n^2 2^2n^2 2n^2 n^2[/tex]

الان با توجه به معادله به دست اومده میتونیم روند کلی معادله رو حدس بزنیم تنها چیزی که میمونه اینه که جمله آخر رو به دست بیاریم اونم اینطوری به دست میاد که با توجه به اینکه آخرین جمله همون T(1)=1 یعنی ما تاجایی پیش میریم که به یک برسیم

[tex]T(\frac{n}{2^i})=T(1)=1->(\frac{n}{2^i})=1->2^i=n->(2^i)=\log n->i=\log n[/tex]

با توجه به معادله آخری داریم:

[tex]ُT(n)=n^2 2n^2 2^2n^2 2^3n^2 2^4n^2 ... 2^{\log n-1}n^2 8\log n[/tex]

درباره جمله یکی مانده به آخر که دورش خط کشیده بودین این جمله بر اساس جملات قبلی به دست میاد و توانش هم اینطوری محاسبه میشه:

[tex]\frac{n}{2^i}=2->2\times2^i=n->2^{i 1}=n->\log2^{i 1}=\log n->i 1=\log n->i=\log n-1[/tex]

الان تا جمله یکی مانده به آخر تشکیل یه سری میده که از صفر تا توان همون جمله یکی مانده به آخر هستش و جمله آخری هم خودش رو مینویسیم و اینطوری میشه:

[tex]Sigma^{k=\log n-1}_{k=0}2^kn^2 8\log n[/tex]

چون بین معادله جمع هست مرتبه هر کدوم رو جداگانه به دست میاریم و اونی که بزرگتره مرتبه معادله اصلی میشه الان اینجا هر دو از مرتبه ان به توان سه هستن پس همون ان به توان سه میشه.

پاسخ:

خیلی ممنون عالی بود