زمان کنونی: ۱۳ تیر ۱۳۹۹, ۰۲:۲۳ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

پیچیدگی زمانی به روش ترسیم درخت

ارسال:
  

wskf پرسیده:

پیچیدگی زمانی به روش ترسیم درخت

دوستان چه جوری میاد ارتفاع درخت رو تشخیص میده و پیچیدگی زمانی رو بدست میاره .
مثلا تو این مثال :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

مدرسان خیلی بد توضیح داده .
اگه کسی واضخ ترش می دونه توضیح بده لطفا
نقل قول این ارسال در یک پاسخ

۵
ارسال:
  

Pure Liveliness پاسخ داده:

RE: پیچیدگی زمانی به روش ترسیم درخت

سلام.
اول ریشه ی درخت رو میبینیم که هزینه ش چقدر هست. که [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]
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

wskf پاسخ داده:

RE: پیچیدگی زمانی به روش ترسیم درخت

عالی بود مرسی ..
موفق باشیم
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Saman پاسخ داده:

RE: پیچیدگی زمانی به روش ترسیم درخت

......
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۶,۸۵۱ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۲,۶۰۹ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی Sanazzz ۱۷ ۴,۵۱۷ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱۱۶ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  تعداد روش های نوشتن عدد n ss311 ۲ ۳۸۸ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  تعداد درخت فراگیر ss311 ۰ ۲۱۸ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  مشاوره روش تحقیق و تحلیل آماری sirvan.t ۰ ۲۵۶ ۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ
آخرین ارسال: sirvan.t
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۸۶۱ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۲ ۱,۲۳۸ ۰۷ مهر ۱۳۹۸ ۰۶:۴۵ ب.ظ
آخرین ارسال: hamzadebaroon
  درخت دسترس پذیری برای شبکه های پتری αɾια ۱ ۵۰۳ ۰۹ تیر ۱۳۹۸ ۰۶:۳۰ ب.ظ
آخرین ارسال: αɾια

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close