(۱۶ تیر ۱۳۹۴ ۰۷:۰۱ ب.ظ)mahnaz.p نوشته شده توسط:  

(16 تیر ۱۳۹۴ ۰۲:۴۳ ب.ظ)LEA3C نوشته شده توسط:  سلام دوستان
لطفا کسی میتونه توضیح بده که تحلیل سرشکنی برای کاهش یک عدد دودویی k بیتی چطوریه.
جوابش (O(k میشه اما دلیلش رو نمیدونم
پیشاپیش ممنون

سلام.فکر کنم سوالاتون اشتباه باشه عمل کاهش به تنهایی اگر باشه مثل عمل افزایش در تحلیل سرشکنی هزینش O(1 هست ولی اگر عمل کاهش و افزایش رو باهم داشته باشیم هزینه اوی K میشه .دلیلشم اینه ک شما مثلا در نظر بگیرید تمام بیت ها ۱ باشه یک افزایش ک بدیم تمام بیت ها صفر میشن و هزینه k حالا عمل بعدی اگر کاهش باشه تمام بیت ها ۱ میشن و هزینه k داره همینجوری یکی در میون اینکارو انجام میدیم هربار هزینه k داره.