سلام
من نمیتونم مرتبه زمانی این تابع رو حل کنم میشه یکی کمکم کنه؟
t(n)=t(n/2)+t(n-1)+n
سلام اگه جمله t(n/2) رو در نظر نگیریم(ارتفاع درخت به چمله t(n-1)بستگی داره ) میمونه t(n)=t(n-1)+n که O(n^2) داره
پس میشه گفت (T(n)>= O(n^2
(۱۵ مهر ۱۳۹۲ ۰۴:۰۵ ق.ظ)black_knight نوشته شده توسط: سلام اگه جمله t(n/2) رو در نظر نگیریم(ارتفاع درخت به چمله t(n-1)بستگی داره ) میمونه t(n)=t(n-1)+n که O(n^2) داره
پس میشه گفت (T(n)>= O(n^2
سلام ممنونم از کمکتون.
یعنی مشکلی وجود نداره اگه t(n/2 رو حذف کنیم؟
ممکنه این n عدد بزرگی باشه!
چون t(n/2) ازt(n-1) کوچیکتره حذفش کردید؟
(۱۵ مهر ۱۳۹۲ ۰۲:۴۹ ب.ظ)shokofe نوشته شده توسط:سلام(15 مهر ۱۳۹۲ ۰۴:۰۵ ق.ظ)black_knight نوشته شده توسط: سلام اگه جمله t(n/2) رو در نظر نگیریم(ارتفاع درخت به چمله t(n-1)بستگی داره ) میمونه t(n)=t(n-1)+n که O(n^2) داره
پس میشه گفت (T(n)>= O(n^2
سلام ممنونم از کمکتون.
یعنی مشکلی وجود نداره اگه t(n/2 رو حذف کنیم؟
ممکنه این n عدد بزرگی باشه!
چون t(n/2) ازt(n-1) کوچیکتره حذفش کردید؟
خواهش می کنم
می دونید خوب میشه گفت ارتفاع درختمون به جمله t(n-1) بستگی داره حالا هر چی این n بزرگتر بشه معلومه که ارتفاع واسه جمله t(n-1) بیشتره
مثلا واسه ۵۱۲ جمله t(n-1) ، باعث ایجاد ارتفاع ۵۱۲ میشه اما لگاریتمیه فقط ۹
پس میشه یه جورایی تخمین زد
البته من مطمئن نیستم دوستان هم اگه نظر بدن که چه بهتر
این منفی واسه چیه؟خوب داداش من اگه می بینی جواب اشتباس بیا درستشو بزار ما هم یه چیزی یاد می گیریم!
سلام. منم با جوابتون موافقم. مقدارش متناسب با همون (t(n-1 میشه. از روی درخت بازگشت خیلی راحت مشخص میشه.
مرسی از همتون
من اینجوری حساب کردم حداکثرش میشه
t(n-1)+t(n-1)+n=2t(n-1)+n که میشه n^2
یه بارم حداقلش
t(n/2)+t(n/2)+n=2t(n/2)+n که میشه nlogn
پس میشه کوچکتر مساوی n به توان ۲ و بزرگتر مساوی nlogn
این جوری غلطه؟ ممنون از راهنماییهاتون
همون [tex]\theta (n^2)[/tex] میشه.
(۱۵ مهر ۱۳۹۲ ۱۰:۳۳ ب.ظ)Jooybari نوشته شده توسط: همون [tex]\theta (n^2)[/tex] میشه.
ممنونم لطف کردید.
(۱۵ مهر ۱۳۹۲ ۱۰:۳۳ ب.ظ)Jooybari نوشته شده توسط: همون [tex]\theta (n^2)[/tex] میشه.
ممنون میشم توضیح بدین چرا این میشه؟؟
(۲۹ آبان ۱۳۹۲ ۰۱:۳۲ ق.ظ)arezoo174 نوشته شده توسط:(15 مهر ۱۳۹۲ ۱۰:۳۳ ب.ظ)Jooybari نوشته شده توسط: همون [tex]\theta (n^2)[/tex] میشه.
ممنون میشم توضیح بدین چرا این میشه؟؟
عذرخواهی میکنم. توی جوابم عجله کردم. اگه درخت بازگشت رو تشکیل بدیم خواهیم داشت:
[tex]T(n)=T(n-1) T(n/2) n=T(n-2) 2T(n/2) n n-1=T(n 3) ...=T(n 4) ...=T(n/2 1) ...[/tex]
اشتباهی که کردم اون [tex]T(n/2)[/tex] رو در مقابل [tex]T(n-1)[/tex] درنظر نگرفتم. ولی تعدادشون زیاد میشه. اگه تا n/2 مرحله جلو بریم به n/2 تا از این جملات میرسیم. در واقع داریم:
[tex]3n^2/8 nT(n/4)/2<T(n)<3n^2/8 nT(n/2)/2[/tex]
با این اوصاف به نظرم حد بالا برای T میشه [tex](n/8)^{lgn}=n^{lgn-3}[/tex] و حد پایینشم میشه [tex](n/32)^{lgn/2}=n^{lgn-5}[/tex].
(۲۹ آبان ۱۳۹۲ ۱۱:۲۳ ق.ظ)Jooybari نوشته شده توسط:سلام(29 آبان ۱۳۹۲ ۰۱:۳۲ ق.ظ)arezoo174 نوشته شده توسط:(15 مهر ۱۳۹۲ ۱۰:۳۳ ب.ظ)Jooybari نوشته شده توسط: همون [tex]\theta (n^2)[/tex] میشه.
ممنون میشم توضیح بدین چرا این میشه؟؟
عذرخواهی میکنم. توی جوابم عجله کردم. اگه درخت بازگشت رو تشکیل بدیم خواهیم داشت:
[tex]T(n)=T(n-1) T(n/2) n=T(n-2) 2T(n/2) n n-1=T(n 3) ...=T(n 4) ...=T(n/2 1) ...[/tex]
اشتباهی که کردم اون [tex]T(n/2)[/tex] رو در مقابل [tex]T(n-1)[/tex] درنظر نگرفتم. ولی تعدادشون زیاد میشه. اگه تا n/2 مرحله جلو بریم به n/2 تا از این جملات میرسیم. در واقع داریم:
[tex]3n^2/8 nT(n/4)/2<T(n)<3n^2/8 nT(n/2)/2[/tex]
با این اوصاف به نظرم حد بالا برای T میشه [tex](n/8)^{lgn}=n^{lgn-3}[/tex] و حد پایینشم میشه [tex](n/32)^{lgn/2}=n^{lgn-5}[/tex].
آقای جویباری فک کنم یه اشتباه در عبارت زیر انجام دادید:
[tex]T(n)=T(n-1) T(n/2) n=T(n-2) 2T(n/2) n n-1=T(n 3) ...=T(n 4) ...=T(n/2 1) ...[/tex]
که t(n به این شکل باز میشه:
[tex]T(n)=T(n-1) T(n/2) n=T(n-2) T((n-1)/2) (n-1) T((n-2)/2) T(n/4) n/2 n=...[/tex]
T(n-1) > T(n/2)
T(n)>2T(n-1)+N
اگر در نظر بگیریم میشه خطی ناهمگن که جوابش میشه ۲به توان n
شما چطور می‌گید میشه n به توان ۲
(۲۹ آبان ۱۳۹۲ ۰۱:۳۳ ب.ظ)pooyaa نوشته شده توسط: سلام
آقای جویباری فک کنم یه اشتباه در عبارت زیر انجام دادید:
[tex]T(n)=T(n-1) T(n/2) n=T(n-2) 2T(n/2) n n-1=T(n 3) ...=T(n 4) ...=T(n/2 1) ...[/tex]
که t(n به این شکل باز میشه:
[tex]T(n)=T(n-1) T(n/2) n=T(n-2) T((n-1)/2) (n-1) T((n-2)/2) T(n/4) n/2 n=...[/tex]
سلام. کاری که کردم فقط جمله n-1 و n-2 و n-3 و ... تا n+1-n/2 بسط دادم. دیگه جمله n/2 و ۲/(n-1) رو باهم مشابه گرفتم. بعد گفتم n/2 از این جملات داریم. این جملات بین n/2 و n/4 هستن. حد بالا همه رو n/2 گرفتم و حد پایین همه رو n/4 گرفتم.
با سلام. جوابتون تو لینک زیر هست:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
موفق باشید.