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

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

ارسال:
  

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: پیچیدگی زمانی به روش ترسیم درخت

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۴۰ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۴۱ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۲ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۲۰۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۱ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۱۳۳ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۵۶۸ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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