(۰۹ بهمن ۱۳۹۵ ۰۲:۳۰ ب.ظ)Pure Liveliness نوشته شده توسط:  سلام.
باید هزینه ی عمل ها رو توی بدترین حالت حساب کنیم و به تعداد تقسیم کنیم تا هزینه ی استهلاکی هر عمل به دست بیاد.
هزینه ی عمل ۱: ۱
هزینه ی عمل ۲: ۲
هزینه ی عمل ۳: ۱
هزینه ی عمل ۴: ۴
هزینه ی عمل ۵: ۱
هزینه ی عمل ۶: ۱
هزینه ی عمل ۷: ۱
هزینه ی عمل ۸: ۸
هزینه ی عمل ۹: ۱
.
.
.
هزینه ی عمل nام: ؟

همونطور که توی صورت سوال گفته هزینه ی عمل i ام اگر i توانی از دو باشه برابر i هست.
خب این توان دو ها یه دنباله رو تشکیل میدن:
[tex]۲^۰+۲^۱+۲^۲+۲^۳+...+۲^k[/tex] که خب میدونیم که [tex]2^k[/tex] حداکثر برابر با n هست. چون هزینه ی عمل nام اگر n توانی از دو باشه برابر با n یا همون [tex]2^k[/tex] میشه و در غیر اینصورت میشه ۱.
خب این جمع هزینه ی اعمالی هست که هزینه شون ۱ نیست که میشه:
[tex]2^0+2^1+...+2^k=\frac{(2^{k+1}-1)}{2-1}=2^{k+1}-1[/tex]
ولی تعداد اون اعمالی که هزینه شون ۱ هست چند تاست؟
کلا n تا عمل بود. k+1 تاش هزینه شون توان دو بود. چرا؟ دنباله رو نگاه کنید از ۰ تا k میشه k+1
پس کلا هزینه ی اعمال با هزینه ی ۱ میشه [tex]n-(k+1)[/tex] یعنی به تعدادشون.
کل هزینه هامون تقسیم بر تعداد میشه:
[tex]\frac{[2^{k+1}-1+(2^{k}-k+1)]}{n=2^k}=\frac{2^{k+1}}{2^k}-\frac{1}{2^k}+\frac{2^{k}-(k+1)}{2^k}=2-0+1+0[/tex] اون دو تا وقتی k بزرگ بشه به ۰ میل میکنن. پس هزینه ی استهلاکی هر عمل برابر با c+3 هست. (اگه آخرش اشتباه نکرده باشم.)

(۰۹ بهمن ۱۳۹۵ ۰۳:۰۱ ب.ظ)hasanmousavi نوشته شده توسط:  

(09 بهمن ۱۳۹۵ ۰۲:۳۰ ب.ظ)Pure Liveliness نوشته شده توسط:  …..
کل هزینه هامون تقسیم بر تعداد میشه:
[tex]\frac{[2^{k+1}-1+(2^{k}-k+1)]}{n=2^k}=\frac{2^{k+1}}{2^k}-\frac{1}{2^k}+\frac{2^{k}-(k+1)}{2^k}=2-0+1+0[/tex] اون دو تا وقتی k بزرگ بشه به ۰ میل میکنن. پس هزینه ی استهلاکی هر عمل برابر با c+3 هست. (اگه آخرش اشتباه نکرده باشم.)

داداش فکر می کنم آخرش اشتباه شد فکر می کنم از جملات کوچکتر در صورت صرف نظر میشه
جواب میشه ۲ .