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