![]() |
پیچیدگی زمانی به روش ترسیم درخت - نسخهی قابل چاپ |
پیچیدگی زمانی به روش ترسیم درخت - wskf - 07 مهر ۱۳۹۵ ۱۱:۲۸ ق.ظ
دوستان چه جوری میاد ارتفاع درخت رو تشخیص میده و پیچیدگی زمانی رو بدست میاره . مثلا تو این مثال : مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید. مدرسان خیلی بد توضیح داده . اگه کسی واضخ ترش می دونه توضیح بده لطفا |
RE: پیچیدگی زمانی به روش ترسیم درخت - Pure Liveliness - 07 مهر ۱۳۹۵ ۱۲:۲۰ ب.ظ
سلام. اول ریشه ی درخت رو میبینیم که هزینه ش چقدر هست. که [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] |
RE: پیچیدگی زمانی به روش ترسیم درخت - Saman - 07 مهر ۱۳۹۵ ۰۱:۰۷ ب.ظ
...... |
RE: پیچیدگی زمانی به روش ترسیم درخت - wskf - 07 مهر ۱۳۹۵ ۰۸:۴۷ ب.ظ
عالی بود مرسی .. موفق باشیم |