با سلام
نحوه حل اینطور سوالا برام یه خرده سخته! مثلا این سوال
[tex]T(N)=T(\frac{\mathrm{n} }{\mathrm{9} }) T(\frac{\mathrm{8n} }{\mathrm{9} }) \Theta (n)[/tex]
پیچیدگیش چطور حساب میشه؟!
ممنون از دوستانی که پاسخ میدن.
سلام دوست عزیز واقعا متاسفم
این بحث زیاد پیچیده نیست اما توضیح دادنش اونم به صورت مجازی واقعا کار مشکلیه و حتی برای من غیره ممکن. حتی سعی کردم با شکل براتون حل کنم اما باز هم نشد
شما باید از 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 در پایه ۹/۸ فکر میکنم
میبینید توضیحش چقدر سخته
(۱۲ بهمن ۱۳۹۲ ۰۱:۴۰ ب.ظ)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 مرسی که وقت گذاشتین جواب دادین.
حب اگه متوجه شدین که خدا رو شکر
خواهش میکنم
بله میشه nlogn البته دقیقترش میشه n لگاریتم n در پایه ۹/۸
این بحث با درخت حل میشه اگه نشد حتما با قضیه akkra bazi حل میشه خوراک akkra bazi هست
(۱۲ بهمن ۱۳۹۲ ۰۶:۰۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط: این بحث با درخت حل میشه اگه نشد حتما با قضیه akkra bazi حل میشه خوراک akkra bazi هست
یه دنیا ممنونم دوست خوبم
واقعا روش عالی هست، بار اول بود می شنیدم. بازم مرسی
(۱۲ بهمن ۱۳۹۲ ۰۸:۴۱ ب.ظ)sajaddandy نوشته شده توسط:(12 بهمن ۱۳۹۲ ۰۶:۰۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط: این بحث با درخت حل میشه اگه نشد حتما با قضیه akkra bazi حل میشه خوراک akkra bazi هست
یه دنیا ممنونم دوست خوبم
خواهش میکنم