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

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

ارسال:
  

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