من به سختی گزینه ۴ رو بدست آوردم، کسی یه راه آسون و سریع میدونه؟
اینو با تغییر متغیر n=2^m حل کن به شکل f(m)=3/2 f(m-1) -1/2 f(m-2) -(1/2)^m در میاد...
البته به نظرم میشه گفت چون تو درخت بازگشتی هزینه هر مرحله تتا یک بروی n هست (منفی)
اگه تو هر مرحله هزینه اون مرحله رو حساب کنی (میشه منفی یک بروی n) حالا باید ارتفاع درخت ضربدر هزینه هر مرحله بکنی
این با یک نگاه هون اول به درخت میتونی بفمهمی
کد:
(۳/۲×۲/n)-(1/2×۴/n)=1/nحالا هر وقت یه همچین درختی دیدی که هزینه هر سطح برابره کافیه ارتفاعو ضربدرش کنی...
ارتفاع درخته چقده ؟ log n
حالا دقت کن فرزندای درخت چطوری پیشرفت میکنن میان پایین ؟ کسری که مخرجش هی داره بیشتر میشه
هزینه درخت چی میشه؟ یه ضرب ساده
