از دوستان محترم کسی میدونه چرا مرتبه T(n)= T(n-1))+1/n میشه تتای Lnn ؟
lim (n ->binahayat)( 1 + 1/2 + 1/3 + 1/4 + ... + 1/n - ln(n) )= 0.5772156649
یعنی وقتی n به سمت بی نهایت میل میکنه حاصل این سری به lnn نزدیک میشه. (حاصل این سری مرتبه الگوریتم بالاست)
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
من با اجازه یه نکته ای به راه حلی که afagh1389 توضیح دادن اضافه کنم:
اگه درخت بازگشتیش رو بکشید، اون سری ای که ایشون گفتن به دست میاد. به خاطر همین جوابش میشه جواب اون سری!
درخت بازگشتیش این طوریه:
منم یه نکته بگم:
با اجازه دوستان:
از لحاظ حدی وقتی n به سمت بینهایت بره سیگما معادل میشه با انتگرال بنابراین
اینگونه اثبات میشود: (در فایل ضمیمه ببینید )
در ضمن به این سری میگن سری همسازه
