(۱۷ دى ۱۳۹۳ ۰۹:۰۵ ق.ظ)Ametrine نوشته شده توسط: مرسی
من تو روش جایگزینی گیر میکنم.
در رابطه ی آخر چرا T(n2) رو حذف کردید؟
ببینید درست میگم؟
یه قسمت میشه n2
یه قسمت دیگه میشه 12n2
درسته؟
بعد چون دومی ضریب داره رشدش سریعتره آره؟
به این دلیل که رابطه بازگشتی از دو قسمت تشکیل شده یکی
T(n−1) و اون یکی هم
T(n2) بین این دوتا هم جمع هست. پس وقتی بخوایم پیچیدگی رابطه رو حساب کنیم اونی که زمان بیشتری میبره مشخص کنه پیچیدگی رابطه هست. الان بین این دو تا
T(n2) سرعت بیشتری داره پس میزاریمش کنار و مثل اینه که رابطه اینطوری باشه
T(n)=T(n−1)n.
دقیقا توی درخت بازگشتی از همین روش برای مشخص کردن ارتفاع درخت استفاده میشه. اونجام به همین دلیل هستش.
موفق باشید