۱
subtitle
ارسال: #۱
حل پیچیدگی به روش درخت تجزیه
با سلام
نحوه حل اینطور سوالا برام یه خرده سخته! مثلا این سوال
[tex]T(N)=T(\frac{\mathrm{n} }{\mathrm{9} }) T(\frac{\mathrm{8n} }{\mathrm{9} }) \Theta (n)[/tex]
پیچیدگیش چطور حساب میشه؟!
ممنون از دوستانی که پاسخ میدن.
نحوه حل اینطور سوالا برام یه خرده سخته! مثلا این سوال
[tex]T(N)=T(\frac{\mathrm{n} }{\mathrm{9} }) T(\frac{\mathrm{8n} }{\mathrm{9} }) \Theta (n)[/tex]
پیچیدگیش چطور حساب میشه؟!
ممنون از دوستانی که پاسخ میدن.
۲
ارسال: #۲
RE: حل پیچیدگی به روش درخت تجزیه
سلام دوست عزیز واقعا متاسفم
این بحث زیاد پیچیده نیست اما توضیح دادنش اونم به صورت مجازی واقعا کار مشکلیه و حتی برای من غیره ممکن. حتی سعی کردم با شکل براتون حل کنم اما باز هم نشد
شما باید از n شروع کنید و بیاید به سمت برگ ها. یعنی برگ های n میشن n/9 و ۸n/9 حالا دوباره واسه اینا. برگ های n/9 میشن n/81 و ۸n/81 . برگ های ۸n/9 میشن ۸n/81 و ۶۴n/81 و ....
حالا اگه جمع هر سطر رو حساب کنید میبینید که میشه n
بعد باید ارتفاع درخت رو به دست بیارید اما این درخت متوازن نیست یعنی سمت چپ درخت ارتفاعش کمتره تا سمت راسته درخت
پس هزینتون میشه بین ارتفاع سمت چپ * n و ارتفاع سمت راست * n
البته این شاید بشه گفت که Teta هست و میشه گفت از مرتبه O همون سمت راست * n هستش
که ارتفاع سمت راست هم میشه لگاریتم n در پایه ۹/۸ فکر میکنم
میبینید توضیحش چقدر سخته
این بحث زیاد پیچیده نیست اما توضیح دادنش اونم به صورت مجازی واقعا کار مشکلیه و حتی برای من غیره ممکن. حتی سعی کردم با شکل براتون حل کنم اما باز هم نشد
شما باید از n شروع کنید و بیاید به سمت برگ ها. یعنی برگ های n میشن n/9 و ۸n/9 حالا دوباره واسه اینا. برگ های n/9 میشن n/81 و ۸n/81 . برگ های ۸n/9 میشن ۸n/81 و ۶۴n/81 و ....
حالا اگه جمع هر سطر رو حساب کنید میبینید که میشه n
بعد باید ارتفاع درخت رو به دست بیارید اما این درخت متوازن نیست یعنی سمت چپ درخت ارتفاعش کمتره تا سمت راسته درخت
پس هزینتون میشه بین ارتفاع سمت چپ * n و ارتفاع سمت راست * n
البته این شاید بشه گفت که Teta هست و میشه گفت از مرتبه O همون سمت راست * n هستش
که ارتفاع سمت راست هم میشه لگاریتم n در پایه ۹/۸ فکر میکنم
میبینید توضیحش چقدر سخته
ارسال: #۳
RE: حل پیچیدگی به روش درخت تجزیه
(۱۲ بهمن ۱۳۹۲ ۰۱:۴۰ ب.ظ)hosshah نوشته شده توسط: سلام دوست عزیز واقعا متاسفم
این بحث زیاد پیچیده نیست اما توضیح دادنش اونم به صورت مجازی واقعا کار مشکلیه و حتی برای من غیره ممکن. حتی سعی کردم با شکل براتون حل کنم اما باز هم نشد
شما باید از n شروع کنید و بیاید به سمت برگ ها. یعنی برگ های n میشن n/9 و ۸n/9 حالا دوباره واسه اینا. برگ های n/9 میشن n/81 و ۸n/81 . برگ های ۸n/9 میشن ۸n/81 و ۶۴n/81 و ....
حالا اگه جمع هر سطر رو حساب کنید میبینید که میشه n
بعد باید ارتفاع درخت رو به دست بیارید اما این درخت متوازن نیست یعنی سمت چپ درخت ارتفاعش کمتره تا سمت راسته درخت
پس هزینتون میشه بین ارتفاع سمت چپ * n و ارتفاع سمت راست * n
البته این شاید بشه گفت که Teta هست و میشه گفت از مرتبه O همون سمت راست * n هستش
که ارتفاع سمت راست هم میشه لگاریتم n در پایه ۹/۸ فکر میکنم
میبینید توضیحش چقدر سخته
مرسی دوست من، مشکل من قسمت محاسبه ارتفاعش بود که بعضی سوالا اشتباه حل میکنم! تقریبا متوجه شدم که چطور حساب میشه... جوابش میشه O(nlgn) ...l مرسی که وقت گذاشتین جواب دادین.
ارسال: #۴
RE: حل پیچیدگی به روش درخت تجزیه
حب اگه متوجه شدین که خدا رو شکر
خواهش میکنم
بله میشه nlogn البته دقیقترش میشه n لگاریتم n در پایه ۹/۸
خواهش میکنم
بله میشه nlogn البته دقیقترش میشه n لگاریتم n در پایه ۹/۸
۰
ارسال: #۵
RE: حل پیچیدگی به روش درخت تجزیه
این بحث با درخت حل میشه اگه نشد حتما با قضیه akkra bazi حل میشه خوراک akkra bazi هست
ارسال: #۶
RE: حل پیچیدگی به روش درخت تجزیه
ارسال: #۷
RE: حل پیچیدگی به روش درخت تجزیه
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| تعداد برگ درخت؟؟؟؟؟؟؟ | rad.bahar | ۴ | ۴,۹۱۱ |
۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ آخرین ارسال: mohamadrra |
|
| دو سوال در مورد درخت BST(درخت جستجوی دودویی) | امیدوار | ۳ | ۵,۶۵۰ |
۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ آخرین ارسال: marzi.pnh |
|
| زمان جستجوی درخت | fateme.sm | ۰ | ۱,۷۹۵ |
۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ آخرین ارسال: fateme.sm |
|
| مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۴۱۶ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
| عمق درخت ???? | rad.bahar | ۱ | ۲,۴۳۶ |
۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ آخرین ارسال: عزیز دادخواه |
|
| محاسبه ارتفاع درخت.... | baharkhanoom | ۳ | ۸,۱۷۱ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ آخرین ارسال: mohsentafresh |
|
| پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت | اsepid8994 | ۰ | ۱,۸۱۹ |
۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ آخرین ارسال: اsepid8994 |
|
| تعداد روش های نوشتن عدد n | ss311 | ۲ | ۳,۴۱۱ |
۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ آخرین ارسال: ss311 |
|
| تعداد درخت فراگیر | ss311 | ۰ | ۲,۳۳۹ |
۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ آخرین ارسال: ss311 |
|
| مشاوره روش تحقیق و تحلیل آماری | sirvan.t | ۰ | ۲,۱۹۳ |
۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ آخرین ارسال: sirvan.t |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close