اگه درخت رابطه رو رسم کنید، می‌بینید که توی سطح دوم تعداد کل عناصر ما شده $\frac{n}{5} \frac{7n}{10} 6\approx \frac{9n}{10}$ (از مقدار ۶ در برابر ۹n/10 میشه صرف نظر کرد). چون هزینه‌ی عملیات هر سطح مستقیماً با تعداد عناصر نسبت خطی داره (به عبارت دیگه چون $f(n)$ در این رابطه‌ی بازگشتی برابر است با $\Theta(n)$)، پس هزینه‌ی سطح دوم هم تقریباً برابر میشه با $\frac{9n}{10}$. به همین شکل تعداد عناصر و هزینه‌ی سطح سوم برابر میشه با $(\frac{9}{10})^{2}n$ و با ادامه‌ی این روند هزینه (و تعداد عناصر) سطح i ام میشه $(\frac{9}{10})^{i-1}n$ و...

حال اگر هزینه‌ی همه‌ی سطح‌ها را برای محاسبه‌ی کل مرتبه جمع ببندیم، داریم:
$T(n)\simeq n \frac{9}{10}n (\frac{9}{10})^{2}n ... (\frac{9}{10})^{i-1}n ...=\sum_{i=0}^{\infty}(\frac{9}{10}n)^{i}=\frac{n}{1-\frac{9}{10}}=10n=\Theta(n)$

بنابراین مرتبه‌ی کل این رابطه برابر است با $\Theta(n)$.

$\sum_{i=0}^{\\infty }(9n/10)^{i}=n/(1-9/10)$
اینجا رو میشه بگید چور حساب کردین؟؟؟

(۰۳ مهر ۱۳۹۲ ۰۱:۴۵ ق.ظ)Mahtab.R نوشته شده توسط:  $\sum_{i=0}^{\\infty }(9n/10)^{i}=n/(1-9/10)$
اینجا رو میشه بگید چور حساب کردین؟؟؟

تصاعد هندسی هست دوست عزیز ...

(۰۳ مهر ۱۳۹۲ ۰۱:۴۵ ق.ظ)Mahtab.R نوشته شده توسط:  $\sum_{i=0}^{\\infty }(9n/10)^{i}=n/(1-9/10)$
اینجا رو میشه بگید چور حساب کردین؟؟؟

همونطور که آقای reza6966 فرمودند این یک تصاعد هندسی هستش. برای یادآوری تصاعد هندسی به صورت زیر حساب میشه:

$\sum_{i=0}^{\infty}a(q)^{i}=\frac{a}{1-q}$

در مورد تصاعد بالا، $a=n$ و $q = 9/10$ :-)

(۰۳ مهر ۱۳۹۲ ۱۰:۴۲ ق.ظ)azk84 نوشته شده توسط:  

(03 مهر ۱۳۹۲ ۰۱:۴۵ ق.ظ)Mahtab.R نوشته شده توسط:  $\sum_{i=0}^{\\infty }(9n/10)^{i}=n/(1-9/10)$
اینجا رو میشه بگید چور حساب کردین؟؟؟

همونطور که آقای reza6966 فرمودند این یک تصاعد هندسی هستش. برای یادآوری تصاعد هندسی به صورت زیر حساب میشه:

$\sum_{i=0}^{\infty}a(q)^{i}=\frac{a}{1-q}$

در مورد تصاعد بالا، $a=n$ و $q = 9/10$ :-)

این n باید بیرون این توان i باشه،بخاطر همین قاطی کردم.مرسی دوستان
این کلید سپاس هم نیست!!!!سپاس سپاس...