[tex]t(n)=t(\left \lceil n/5 \right \rceil) t(7n/(10) 6) \Theta (n)[/tex]
اگه درخت رابطه رو رسم کنید، می‌بینید که توی سطح دوم تعداد کل عناصر ما شده [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 باشه،بخاطر همین قاطی کردم.مرسی دوستان
این کلید سپاس هم نیست!!!!سپاس سپاس...