۱
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