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

حال اگر هزینه‌ی همه‌ی سطح‌ها را برای محاسبه‌ی کل مرتبه جمع ببندیم، داریم:
[tex]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)[/tex]

بنابراین مرتبه‌ی کل این رابطه برابر است با [tex]\Theta(n)[/tex].

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

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

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

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

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

[tex]\sum_{i=0}^{\infty}a(q)^{i}=\frac{a}{1-q}[/tex]

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

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

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

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

[tex]\sum_{i=0}^{\infty}a(q)^{i}=\frac{a}{1-q}[/tex]

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

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