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

ابهام در درخت بازگشتی

ارسال:
  

irpersian20 پرسیده:

ابهام در درخت بازگشتی

با درود
دوستان اینجا چرا ۲ به توان لگاریتم n شده؟ چرا به توان؟
چون اگر من به جای ۲ به ۴ برسم. میشه ۴ به توان لگاریتم n
[تصویر:  402437_1a5b_tree.jpg]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

fatemeh69 پاسخ داده:

RE: ابهام در درخت بازگشتی

اون [tex]2^{\log\: n}[/tex] تعداد گره های درخت در سطح آخر است .


دقت کنید تعداد گره ها در سطح صفرم (ریشه) برابر [tex]2^0[/tex] در سطح اول برابر [tex]2^1[/tex] و ... است

درخت [tex]\log\: n[/tex] تا سطح دارد و تعداد برگ ها [tex]2^{\log n}[/tex] است که هر کدام از نودهای درخت پیچیدگی برابر [tex]T(1)[/tex] دارند پس پیچیدگی در سطح آخر برابر است با [tex]T(1)\times2^{\log n}=n[/tex]

پس پیچیدگی سطح آخر هم مانند تمام سطح ها برابر n است
کلا [tex]\log n[/tex] تا سطح داریم پس پیچیدگی کل درخت برابر است با nlogn
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۴,۷۸۸ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۵۸۲ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۷۷۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۷۶ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۳۹۳ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۸,۰۹۵ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  تعداد درخت فراگیر ss311 ۰ ۲,۳۰۸ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
Question یک نکته ابهام marvelous ۶ ۵,۴۲۹ ۰۹ دى ۱۳۹۸ ۰۱:۳۰ ب.ظ
آخرین ارسال: marvelous
  درخت دسترس پذیری برای شبکه های پتری αɾια ۱ ۲,۳۹۸ ۰۹ تیر ۱۳۹۸ ۰۶:۳۰ ب.ظ
آخرین ارسال: αɾια
  سطح و عمق و ارتفاع درخت remove ۵ ۱۱,۳۹۶ ۱۹ اسفند ۱۳۹۷ ۰۴:۲۴ ب.ظ
آخرین ارسال: mstfvi

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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