سلام.
اول ریشه ی درخت رو میبینیم که هزینه ش چقدر هست. که [tex]n^2[/tex] هست. اون رو به عنوان ریشه میگذاریم.
توی این جا ریشه ۸ تا فرزند [tex]T(\frac{n}{2})[/tex] داره. اون ها رو به عنوان فرزندهاش میگذاریم. توی این سطح هزینه رو حساب میکنیم. هر [tex]T(\frac{n}{2})[/tex] هزینه ش هست [tex](\frac{n}{2})^2[/tex] پس هزینه ی این سطح میشه ۸ تا [tex]\frac{n^2}{4}[/tex] و در مجموع هزینه ی این سطح میشه [tex]2n^2[/tex]
توی سطح بعد هر کدوم از فرزندهای سطح قبل ۸ تا فرزند دارند که هر کدوم [tex]T(\frac{n}{4})[/tex] هستند که کلا ۶۴ تا هستند و هزینه ی هر کدوم میشه [tex]\frac{n^2}{16}[/tex] و در مجموع هزینه ی این سطح میشه [tex]4n^2[/tex]
.
.
همونطور که میبینیم هزینه ی سطوح متفاوت هست.
در صورتی که هزینه ی سطح ها با هم برابر باشه هزینه ی کل برابر میشه با ارتفاع درخت ضربدر هزینه ی یک سطح.
اما در اینجا که هزینه ها یکسان نیست و یک تصاعد هندسی رو تشکیل میده هزینه ها رو با هم جمع میکنیم.
[tex]n^2+2n^2+4n^2+8n^2+....+2^kn^2=n^2(2^0+2^1+2^2+....+2^k)[/tex]
حالا k ارتفاع درخت هست. چون همون طور که میبینیم توی سطح یک مقدارش برابر با ۱، توی سطح ۲ مقدارش برابر با ۱ و …. هست.
برای به دست آوردن k (ارتفاع درخت):
درخت تا جایی ادامه پیدا میکنه که برسه به برگ ها یعنی [tex]T(1)[/tex] (گاهاََ ممکنه طبق فرضیات [tex]T(1)[/tex] برگ نباشه و [tex]T(2)[/tex] باشه.
حالا باید ببینم که هر سطح از چه قانونی پیروی میکنه و چطور میرسه به برگ.
توی سطح اول داریم: [tex]T(\frac{n}{2^0})[/tex]
توی سطح دوم داریم: [tex]T(\frac{n}{2^1})[/tex]
توی سطح سوم داریم: [tex]T(\frac{n}{2^۲})[/tex]
…
و به همین ترتیب توی سطح k ام داریم : [tex]T(\frac{n}{2^k})[/tex] وقتی که به [tex]T(1)[/tex] برسیم به برگ ها رسیدیم و درخت تا همین جا ادامه پیدا میکنه این k ارتفاع درخت هست.
باید [tex]T(\frac{n}{2^k})==T(1)[/tex] که میشه: [tex]\frac{n}{2^k}=1\: \: \rightarrow\: n=2^{k\: }\rightarrow k=\log n[/tex]
پس ارتفاع درخت logn هست. (البته دقیق تر بخوایم بگیم چون تعداد سطوح یکی از ارتفاع بیشتر هست و ما اینجا تعداد سطوح (k) رو به دست آوردیم، ارتفاع درخت [tex]\log n\: -1[/tex] هست.
همونطور که حساب کردیم هزینه ی مجموع سطوح میشد : [tex]n^2\times\sum_{k=0}^{k=\log n}2^k[/tex] و البته طبق توضیح بالا اگه بخوایم دقیق تر بگیم k حداکثر [tex]\log n\: -1[/tex] هست.
خب می دونیم: [tex]2^0+2^1+....+2^{\log n-1}=\Sigma_{k=0}^{\log n-1}2^k=2^0\times\frac{(1-2^{\log n-1+1})}{1-2}=(2^{\log n}-1)=\theta(2^{\log n})=(2^{\log_2^n})=n[/tex]
خب پس مرتبه ی تابع (مجموع هزینه های تمام سطوح) میشه:
[tex]n^2\times\: \Sigma_{k=0}^{\log n-1}2^k=n^2\times n=n^3[/tex]
[tex]T(n)=\theta(n^3)[/tex]