تحلیل سرشکن به زبان کنکور: چرا یک عمل گران، میانگین را خراب نمی‌کند

مثال ۱: شمارندهٔ دودویی

یک شمارندهٔ k بیتی داری که از صفر شروع می‌کند و هر بار یکی به آن اضافه می‌کنی. هزینهٔ هر افزایش، تعداد بیت‌هایی است که عوض می‌شوند. بدترین افزایش مثل 0111 به 1000 است که هر چهار بیت را عوض می‌کند. پس با تحلیل ساده، n افزایش O(nk) هزینه دارد. ولی این کران خیلی بدبینانه است.

روش جمعی: هر بیت چند بار عوض می‌شود؟

بیت اول در هر افزایش عوض می‌شود: n بار. بیت دوم یک بار در میان: حدود n/2 بار. بیت سوم حدود n/4 بار، و همین‌طور تا آخر. جمع این‌ها یک سری هندسی است که از 2n کمتر است. پس n افزایش کمتر از 2n بیت عوض می‌کند و هزینهٔ سرشکن هر افزایش O(1) است.

روش حسابداری: هر ۱ شدن، هزینهٔ ۰ شدنش را از قبل می‌دهد

به هر افزایش ۲ واحد شارژ کن. هر افزایش دقیقاً یک بیت را از ۰ به ۱ می‌برد: ۱ واحد برای این کار خرج می‌شود و ۱ واحد روی همان بیت به‌عنوان اعتبار می‌ماند. بعداً وقتی آن بیت از ۱ به ۰ برمی‌گردد، هزینه‌اش را از همین اعتبار می‌دهیم. چون هر ۱ در شمارنده اعتبار خودش را دارد، اعتبار هیچ‌وقت منفی نمی‌شود و هزینهٔ کل حداکثر 2n است.

مثال ۲: آرایهٔ پویا

آرایه‌ای با ظرفیت ثابت داری. هر وقت پر شد، آرایه‌ای بزرگ‌تر می‌سازی و همهٔ عناصر را کپی می‌کنی. همان درجی که کپی را راه می‌اندازد Θ(n) هزینه دارد. سؤال این است که ظرفیت را چقدر بزرگ کنی.

دو برابر کردن ظرفیت

اگر ظرفیت از ۱ شروع شود و هر بار دو برابر شود، کپی‌ها در اندازه‌های ۱، ۲، ۴، … اتفاق می‌افتند و جمعشان از 2n کمتر است. با n درج خود عناصر، هزینهٔ کل کمتر از 3n است و هزینهٔ سرشکن هر درج O(1). در روش حسابداری یعنی به هر درج ۳ واحد شارژ کن: ۱ برای درج خودش، ۱ برای کپی بعدی خودش و ۱ برای کپی یکی از عناصر قدیمی.

زیاد کردن ظرفیت با عدد ثابت

حالا فرض کن هر بار فقط ۱۰ خانه به ظرفیت اضافه کنی. کپی‌ها در اندازه‌های ۱۰، ۲۰، ۳۰، … اتفاق می‌افتند و جمعشان از مرتبهٔ n²/20 است. هزینهٔ کل Θ(n²) و هزینهٔ سرشکن هر درج Θ(n) می‌شود. هر عدد ثابتی به‌جای ۱۰ بگذاری، مرتبه همین است.

قاعده: هر ضریب رشد بزرگ‌تر از ۱، مثل دو یا یک‌ونیم، هزینهٔ سرشکن O(1) می‌دهد؛ فقط ضریب ثابتش فرق می‌کند. اضافه کردن عدد ثابت، هر چقدر هم بزرگ، سرشکن را خطی می‌کند.

مثال ۳: پشته با عمل چندحذفی

پشته‌ای داری که علاوه بر درج و حذف، عمل «k تا حذف کن» هم دارد. یک عمل چندحذفی ممکن است O(n) طول بکشد، پس به نظر می‌رسد n عمل O(n²) هزینه دارد. ولی هر عنصر حداکثر یک بار حذف می‌شود و فقط بعد از اینکه درج شده باشد. پس تعداد کل حذف‌ها، چه تکی چه چندتایی، از تعداد درج‌ها بیشتر نیست. هزینهٔ کل n عمل O(n) است و سرشکن هر عمل O(1).

روش پتانسیل در یک نگاه

در روش پتانسیل به وضعیت ساختمان داده عددی به نام پتانسیل Φ نسبت می‌دهی. هزینهٔ سرشکن هر عمل، هزینهٔ واقعی آن به‌علاوهٔ تغییر پتانسیل است. اگر پتانسیل از صفر شروع کند و هیچ‌وقت منفی نشود، جمع هزینه‌های سرشکن کرانی برای جمع هزینه‌های واقعی است.

برای شمارنده، Φ را تعداد بیت‌های ۱ بگیر. افزایشی که t بیت ۱ را صفر می‌کند و یک بیت را ۱ می‌کند، هزینهٔ واقعی t + 1 دارد و پتانسیل را t − 1 واحد کم می‌کند؛ پس هزینهٔ سرشکنش ۲ است. انتخاب Φ مهم‌ترین قدم است: باید در عمل‌های ارزان کمی زیاد شود تا عمل گران بعدی را جبران کند.

دو اشتباه رایج

اشتباه ۱: کوچک کردن آرایه وقتی نصفش خالی شد

منطقی به نظر می‌رسد: وقتی آرایه پر شد دو برابرش کن و وقتی نصفش خالی شد نصفش کن. ولی اگر آرایه درست روی مرز باشد و درج و حذف یکی در میان بیایند، هر چند عمل یک بار کل آرایه کپی می‌شود. در یک شبیه‌سازی با ۴۰۰۰ عمل روی همین مرز، این روش حدود ۳۶٬۰۰۰ واحد هزینه داشت. راه درست این است که فقط وقتی یک‌چهارم پر شد نصفش کنی؛ با همان ۴۰۰۰ عمل هزینه حدود ۴٬۰۰۰ شد و هزینهٔ سرشکن دوباره O(1) است.

اشتباه ۲: سرشکن O(1) یعنی هر عمل O(1)

نه. سرشکن O(1) یعنی کل n عمل O(n) است، ولی یک عمل خاص می‌تواند Θ(n) طول بکشد. در تستی که می‌پرسد «بدترین زمان یک درج در آرایهٔ پویا» جواب Θ(n) است، نه O(1). در سیستم‌های بی‌درنگ که هیچ عملی نباید طول بکشد، این تفاوت مهم است.

پرسش‌های پرتکرار

تحلیل سرشکن با تحلیل حالت میانگین چه فرقی دارد؟

در حالت میانگین روی ورودی احتمال می‌گذاری و امید ریاضی زمان را حساب می‌کنی. در تحلیل سرشکن هیچ احتمالی نیست: برای بدترین دنبالهٔ n عملی ثابت می‌کنی که هزینهٔ کل از یک کران بیشتر نمی‌شود و آن را بر n تقسیم می‌کنی.

کدام روش تحلیل سرشکن را در تست به کار ببرم؟

در تست‌ها معمولاً روش جمعی سریع‌ترین است: کل هزینه را بشمار و بر n تقسیم کن. روش حسابداری وقتی به کار می‌آید که بتوانی بگویی «هر عنصر هزینهٔ آیندهٔ خودش را از قبل می‌پردازد». روش پتانسیل برای وقتی است که سؤال صریحاً تابع پتانسیل را داده و هزینهٔ سرشکن یک عمل را می‌خواهد.

چرا دو برابر کردن آرایه هزینهٔ سرشکن O(1) دارد؟

چون کپی‌های بزرگ نادرند: بعد از هر کپی به اندازهٔ k، حداقل k درج ارزان لازم است تا کپی بعدی پیش بیاید. جمع کپی‌ها برای n درج از 2n کمتر است، پس هزینهٔ کل کمتر از 3n است.

اگر ظرفیت را سه برابر کنیم چه می‌شود؟

باز هم O(1) سرشکن. هر ضریب رشد ثابت بزرگ‌تر از ۱ کار می‌کند. ضریب بزرگ‌تر کپی کمتری می‌خواهد ولی حافظهٔ خالی بیشتری هدر می‌دهد؛ این یک بده‌بستان است، نه تفاوت در مرتبه.

این مبحث در کلاس

من ارشدم را در دانشگاه صنعتی شریف، در نرم‌افزار با گرایش الگوریتم و محاسبات گرفتم. تحلیل سرشکن، از شمارنده و آرایهٔ پویا تا تابع پتانسیل در ساختمان داده‌های پیشرفته‌تر، بخشی از دورهٔ داده‌ساختار و الگوریتم من است؛ با ویدیو، جزوهٔ کامل و تست‌های حل‌شده. از ۱۲ تست داده‌ساختار و الگوریتم کنکور ۱۴۰۵، نُه‌تا پیش‌تر در کلاس کار شده بود؛ سند این مقایسه در صفحهٔ مستندات هست. دوره‌ها به‌زودی روی همین سایت منتشر می‌شوند و ویدیوی رایگان چند جلسه از کلاس‌هایم هم به‌زودی در صفحهٔ ویدیوهای رایگان همین سایت قرار می‌گیرد.

قدم بعدی تو

این سه سؤال را بدون نگاه به متن جواب بده: ۱) یک شمارندهٔ دودویی را از صفر ۶۴ بار افزایش می‌دهیم؛ کل بیت‌های عوض‌شده کمتر از چند است؟ ۲) آرایهٔ پویایی که ظرفیتش را هر بار ۱۰۰ خانه زیاد می‌کند، برای n درج هزینهٔ کل از چه مرتبه‌ای دارد؟ ۳) در پشتهٔ با چندحذفی، n عمل که نیمی درج و نیمی چندحذفی است، هزینهٔ کل از چه مرتبه‌ای است؟

جواب‌ها: ۱) کمتر از ۱۲۸، یعنی 2n؛ دقیقاً ۱۲۷ بیت. ۲) Θ(n²). ۳) Θ(n).