تالار گفتمان مانشت

سلام
من نمیتونم مرتبه زمانی این تابع رو حل کنم میشه یکی کمکم کنه؟

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

(15 مهر 1392 04:05 ق.ظ)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) کوچیکتره حذفش کردید؟

(15 مهر 1392 02:49 ب.ظ)shokofe نوشته شده توسط: [ -> ]

(15 مهر 1392 04:05 ق.ظ)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) بیشتره
مثلا واسه 512 جمله t(n-1) ، باعث ایجاد ارتفاع 512 میشه اما لگاریتمیه فقط 9
پس میشه یه جورایی تخمین زد
البته من مطمئن نیستم دوستان هم اگه نظر بدن که چه بهتر
این منفی واسه چیه؟خوب داداش من اگه می بینی جواب اشتباس بیا درستشو بزار ما هم یه چیزی یاد می گیریم!

سلام. منم با جوابتون موافقم. مقدارش متناسب با همون (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] میشه.

(15 مهر 1392 10:33 ب.ظ)Jooybari نوشته شده توسط: [ -> ]همون [tex]\theta (n^2)[/tex] میشه.

ممنونم لطف کردید.

(15 مهر 1392 10:33 ب.ظ)Jooybari نوشته شده توسط: [ -> ]همون [tex]\theta (n^2)[/tex] میشه.

ممنون میشم توضیح بدین چرا این میشه؟؟

(29 آبان 1392 01:32 ق.ظ)arezoo174 نوشته شده توسط: [ -> ]

(15 مهر 1392 10:33 ب.ظ)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].

(29 آبان 1392 11:23 ق.ظ)Jooybari نوشته شده توسط: [ -> ]

(29 آبان 1392 01:32 ق.ظ)arezoo174 نوشته شده توسط: [ -> ]

(15 مهر 1392 10:33 ب.ظ)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
اگر در نظر بگیریم می‌شه خطی‌ ناهمگن که جوابش می‌شه 2به توان n

شما چطور می‌گید می‌شه n به توان 2

(29 آبان 1392 01:33 ب.ظ)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 و 2/(n-1) رو باهم مشابه گرفتم. بعد گفتم n/2 از این جملات داریم. این جملات بین n/2 و n/4 هستن. حد بالا همه رو n/2 گرفتم و حد پایین همه رو n/4 گرفتم.

با سلام. جوابتون تو لینک زیر هست:


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


موفق باشید.