(۱۸ دى ۱۳۸۹ ۰۳:۲۷ ب.ظ)حامد نوشته شده توسط:  راه اول:
راه حل اصلی که استفاده از درخت بازگشت هست که این مثال دقیقا توی کتاب پوران هم هست.همیشه برای بدست اوردن ارتفاع می بینیم تابع بازگشتیمون مثلا تقسیم بر k شده ارتفاعمون پس میشه لگاریتم n درمبنای K.اگر بر دو عدد متفاوت تقسیم شده بود مثلا بود t(n/4)+t(n/3 در این صورت K را عدد کوچکتر میگیریم(۳) زیرا دیرتر اون قسمت درخت به برگ میرسه.
پس توی این سوال ارتفاع میشه Lgn.حالا باید مقادیر هر سطح رو جمع بزنید.
سطح اول: n/lgn
سطح دوم‌: n تقسیم بر لگاریتم n دوم= n/lgn-1
سطح سوم‌: n/lgn-2
....
پس جوابمون میشه مجموع این سطوح که تا ارتفاع lgn ادامه دارند:

[tex]n(1/lg n 1/((lg n)-1) ...1/2 1)[/tex]
{قسمت داخل پرانتز اگر n بجای Lgn بود میشد تتای lgn پس حالا میشه تتای lglgn.در نتیجه جواب میشه:تتای nlglgn
راه دوم:
از قضیه اصلی و قضیه اصلی تعمیم یافته نمی شه توی این مساله استفاده کرد ولی یک قضیه‌ی دیگه وجود دارد که شامل اکثر حالات میشه و می تونید از اون استفاده کنید.قضیه مورد نظر را توی یکی از کتابای گسسته که تو گوگل بوک بود دیدم و توی کتاب های کنکوری و مرجع خودمون نیست.
یکی از حالات این قضیه هست که میگه در صورتی که توان n در دو طرف یکی شد و لگاریتم هم توان منفی یک داشت جواب در lglgn ضرب خواهد شد.

(۱۸ دى ۱۳۸۹ ۰۳:۲۷ ب.ظ)حامد نوشته شده توسط:  راه اول:

سطح اول: n/lgn
سطح دوم‌: n تقسیم بر لگاریتم n دوم= n/lgn-1
سطح سوم‌: n/lgn-2
....
پس جوابمون میشه مجموع این سطوح که تا ارتفاع lgn ادامه دارند:

[tex]n(1/lg n 1/((lg n)-1) ...1/2 1)[/tex]
{قسمت داخل پرانتز اگر n بجای Lgn بود میشد تتای lgn پس حالا میشه تتای lglgn.در نتیجه جواب میشه:تتای nlglgn
راه دوم:

(۱۸ دى ۱۳۸۹ ۰۲:۵۹ ب.ظ)afagh1389 نوشته شده توسط:  من فکر میکنم باید تغییر متغیر بدیم مثلا m=logn و n=2^m و .... البته خودم حل نکردم ببینم جواب میده یا نه!