شمارنده‌ی دودویی (تحلیل سرشکن)
یک شمارنده‌ی دودویی را هشت بار یکی زیاد می‌کند؛ یک افزایش ممکن است بیت‌های زیادی را عوض کند، ولی میانگین کمتر از ۲ است.
شمارنده‌ای دودویی با k بیت داریم و آن را بارها یکی زیاد می‌کنیم. یک افزایش بیت‌های ۱ انتهایی را صفر می‌کند (رقم نقلی) و اولین ۰ را یک. در بدترین حالت یک افزایش هر k بیت را عوض می‌کند. پس n افزایش حداکثر n·k تغییر؟
- زمان:
O(k) for one increment of k bits, O(1) amortized - حافظه:
O(1) - CLRS، بخش ۱۶.۱
از ۰ تا ۸: روی هم ۱۵ تغییر بیت برای ۸ افزایش، کمتر از ۲ برای هر افزایش.
def binary_counter(bits):flips = 0for n in range(1, 9):i = 0while i < len(bits):if bits[i] == 0:breakbits[i] = 0flips = flips + 1i = i + 1if i < len(bits):bits[i] = 1flips = flips + 1return flips
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
bits list
Call stack
- binary_counter()خط 1
توضیح
مسئله
شمارنده‌ای دودویی با k بیت داریم و آن را بارها یکی زیاد می‌کنیم. یک افزایش بیت‌های ۱ انتهایی را صفر می‌کند (رقم نقلی) و اولین ۰ را یک. در بدترین حالت یک افزایش هر k بیت را عوض می‌کند. پس n افزایش حداکثر n·k تغییر؟
تحلیل سرشکن
نه. بیت ۰ در هر افزایش عوض می‌شود، بیت ۱ هر دو افزایش یک بار، بیت ۲ هر چهار افزایش یک بار، و همین‌طور. پس روی هم:
n + n/2 + n/4 + … < 2n
هزینه‌ی سرشکن هر افزایش کمتر از ۲ است، با اینکه بعضی افزایش‌ها گران‌اند. این ایده‌ی اصلی تحلیل سرشکن است: هزینه‌ی کل یک دنباله از عمل‌ها، نه بدترین هزینه‌ی یک عمل.
در trace به چه چیزی نگاه کنی
- بیت ۰ (کم‌ارزش‌ترین) در سمت چپ تصویر است.
- با سطح جزئیات «هر دور حلقه» افزایش‌ها را یکی‌یکی ببین و شمار
resetوsetرا با ۲ × ۸ = ۱۶ مقایسه کن.