تحلیل سرشکنی کیست؟ توضیح بده.
تحلیل سرشکنی.در علوم کامپیوتر به خصوص در تحلیل الگوریتم‌ها، تحلیل سرشکنی زمان اجرای میانگین برای هر دستور را در بدترین حالت بدست می‌آورد. تحلیل سرشکنی با متوسط زمان اجرا تفاوت دارد چرا که زمان اجرای هر دستور در بدترین حالت را بیان می‌کند.گاهی به دنبال روشی برای پیدا کردن زمان اجرای یک رویه هستیم. برای این کار، گاهی پیشنهاد می‌شود که به‌طور مستقیم بدترین زمان اجرا را بدست آوریم. این عمل باعث می‌شود که همیشه یک زمان اجرای خیلی زیاد بدست آید. اما تحلیل سرشکنی این امکان را به ما می‌دهد تا زمان اجرایی بسیار نزدیک به زمان اجرای واقعی بدست آوریم.شبه کد تحلیل سرشکنی.اینجا هدف این است که هزینه‌ی یک عمل را بدون توجه به ورودی به دست بیاوریم. مثلاً اگر یک شمارنده بیتی داشته باشیم، هزینه‌ی هر بار زیاد کردن آن برابر است با هزینه‌ی شمردن تا عددی که الان در شمارنده وجود دارد:این روش (تحلیل سرشکنی) در واقع:در این تحلیل از ۳ روش زیر استفاده می‌شود:I. روش انبوههII. روش حسابداریIII. روش تابع پتانسیلهر ۳ روش ذکر شده جواب درستی به ما می دهند و انتخاب استفاده از این ۳ روش بستگی به این دارد که کدام یک برای یک موقعیت خاص مناسب تر باشد.تاریخچه.تحلیل سرشکن شده در ابتدا از روشی به نام تحلیل متراکم پدید آمده که امروزه شامل تحلیل سر شکن است. این تکنیک بار اول توسط رابرت تارجان در مقاله پیچیدگی محاسباتی وقف شده‌اش در سال ۱۹۸۵ معرفی شد. که نیاز به یک شکل مفیدتر از تحلیل روشهای احتمالی متداول مورد استفاده را برطرف می کند. سرشکنی در ابتدا برای انواع خاصی از الگوریتم‌ها مورد استفاده قرار می گرفت، به ویژه آنهایی که مربوط به درختان باینری و عملیات یونیون هستند. با این حال، امروزه هم از این تحلیل کاربرد های زیادی دارد و هنگام تحلیل بسیاری از الگوریتم های دیگر نیز مورد استفاده قرار می گیرد.روش انبوهه.در روش انبوه ابتدا باید هزینه‌ی پی در پی اجرای n عملیات را محاسبه کنیم که در کل هزینه‌ی آن دنباله‌ای از n عملیات است و زمان اجرای آن formula_1 است و سپس آن را بر تعداد (n) تقسیم کرده و در نتیجه هزینهٔ میانگین یا سرشکن شده که برابر "T"("n") / "n" است برای هر عمل بدست می‌آید. برای استفاده از این روش باید هر عمل و هزینهٔ اجرای آن را شناسایی کرد.برای تحلیل شمارنده با این روش این‌گونه در نظر گرفته می‌شود که اگر تغییر بیت‌های در هر مرحله را در نظر بگیریم در مجموع برابر با ۲n و در نتیجه زمان اجرای آن formula_2 می‌شود.روش حسابداری. نوعی از تحلیل انبوه است که به هر عمل یک هزینه‌ی سرشکن شده اختصاص میابد که ممکن است با هزینه‌ی واقعی متفاوت باشد.در این روش در ابتدا یک سری عملیات ابتدایی که در الگوریتم مورد استفاده قرار می‌گیرند را انتخاب می‌کنیم و به صورت دلخواه هزینه‌ی آن‌ها را ۱ در نظر می‌گیریم.به هر مجموعه عملیات یک هزینه نسبت داده می‌شود و عملیاتی که هزینه‌ی کمتری دارند پولشان برای هزینه‌های بعدی ذخیره می‌شود.میزان پول پرداختی برای هر عمل با هزینه‌ی سرشکنی آن متناسب است.برای این داده ساختار به ازای هر عمل ۲ریال هزینه می‌کنیم که این ۲ریال صرف تغییر ۰ به ۱ و بالعکس می‌شود.به صورت کلی هنگامی که هزینه سرشکن شده یک عمل از هزینه واقعی آن تجاوز کند، اختلاف این هزینه به عنوان موجودی به اشیایی مشخص در ساختمان داده اختصاص می‌یابد. موجودی بعداً می‌تواند در جهت کمک به پرداخت برای اعمالی که هزینه سرشکن شده آنها کمتر از هزینه واقعی شان است مورد استفاده قرار گیرد. بنابراین می‌توان هزینه سرشکن شده یک عمل را مشاهده کرد که بین هزینه واقعی آن و موجودی که پرداخت شده یا استفاده می‌شود، تقسیم شده‌است. این روش با تحلیل جمعی که در آن تمام اعمال هزینه‌های سرشکن شده یکسانی دارند، بسیار متفاوت است. هزینه‌های سرشکن شده اعمال باید به دقت انتخاب شوند. اگر بخواهیم تحلیل را با هزینه‌های سرشکن شده انجام دهیم تا نشان دهیم که در بدترین حالت هزینه میانگین هر عمل کم است، کل هزینه سرشکن شده یک توالی از اعمال باید یک حد بالا برای هزینه کل واقعی توالی باشد. علاوه بر این همانند تحلیل جمعی، این رابطه باید برای تمام توالی‌های اعمال برقرار باشد. اگر هزینه واقعی formula_3 امین عمل را با formula_4 و هزینه سرشکن شده formula_3 امین عمل را با formula_6 نشان دهیم، برای تمام توالی‌هایی از عمل formula_7 داریم:formula_8بنا به نامساوی بالا کل موجودی مربوط به ساختمان داده باید در همه زمان‌ها نامنفی باشد. اگر کل موجودی می‌توانست منفی باشد(در نتیجه پرداخت ارزش کم به عمل‌های قبلی، با این تعهد که دوباره پس از آن پرداخت صورت گیرد) آنگاه کل هزینه‌های سرشکن شده ایجاد شده در آن هنگام کمتر از کل هزینه‌های واقعی ایجاد شده می‌بود؛ برای توالی عمل‌ها تا آن زمان کل هزینه سرشکن شده یک حد بالا برای کل هزینه واقعی نمی‌بود. بنابراین باید مراقب باشیم تا موجودی کل در ساختمان داده هرگز منفی نشود.روش شارژ کردن.تعدادی از هزینه را روی اعمال قبلی شارژ می‌کنیم.هزینه‌ی سرشکن: هزینه‌ای که در آینده، بقیه عمل ها روی این عمل شارژ می‌شوند + هزینه‌ای که روی بقیه شارژ می‌کنیم - هزینه‌ی واقعی روش تابع پتانسیل. نوعی از روش حسابداری است که در آن اعتبار ذخیره شده به عنوان تابعی از وضعیت داده ساختار محاسبه می‌شود. هزینه سرشکنی هزینه بدیهی به علاوه تغییر پتانسیل است.راه دیگر پیدا کردن هزینهٔ سرشکنی استفاده از تابع پتانسیل است. در این روش به داده ساختار داده شده یک تابع پتانسیل نسبت می‌دهیم و با یک ساختمان داده اولیه formula_9 را شروع می‌کنیم که روی آن formula_7 عمل انجام می‌شود. برای هر formula_11، formula_12 را هزینه واقعی formula_3 امین عمل قرار می‌دهیم و formula_14 را ساختمان داده‌ای که پس از به کارگیری formula_3 امین عمل روی ساختمان داده formula_16 حاصل می‌شود، قرار می‌دهیم. تابع پتانسیل هر ساختمان داده formula_14 را به یک عدد حقیقی formula_18 نگاشت می‌کند. این عدد، پتانسیل مربوط به ساختمان دادهٔ formula_14 است. هزینه سر شکن شده formula_20 مربوط به formula_21 امین عمل با توجه به تابع پتانسیل formula_22 به صورت زیر تعریف می‌شود:formula_23براین هزینه سرشکن شده هرعمل برابرهزینه واقعی آن به علاوه افزایش پتانسیل حاصل از عمل می‌باشد. بنا به معادله بالا، هزینه سرشکن شده کل formula_7 عمل برابر است با:formula_25اگر بتوانیم یک تابع پتانسیل formula_22 تعریف کنیم بطوریکه formula_27، آنگاه هزینه سرشکن شده کل formula_28، یک حد بالا برای هزینه واقعی کل formula_29 می‌باشد. در عمل همواره نمی‌دانیم چه تعداد عمل ممکن است انجام شود. بنابراین اگر برای تمام formula_3ها تأکید کنیم کهformula_31، آنگاه همانند روش حسابداری تضمین می‌کنیم که از پیش هزینه را پرداخت کرده‌ایم. اغلب مناسب است که formula_32 را 0 تعریف کنیم و آنگاه نشان دهیم که برای تمام formula_3ها، formula_34. به‌طور شهودی اگر اختلاف پتانسیل formula_35 از formula_3 امین عمل مثبت باشد آنگاه هزینه سرشکن شده formula_37 یک پرداخت اضافه به formula_3 امین عمل را نشان می‌دهد، و پتانسیل ساختمان داده افزایش می‌یابد. اگر اختلاف پتانسیل منفی باشد، آنگاه هزینه سرشکن شده، یک پرداخت کم به formula_3 امین عمل را نشان می‌دهد و هزینه واقعی عمل با کاهش پتانسیل پرداخت می‌شود. هزینه‌های سر شکن شده تعریف شده به وسیله دو معادلهٔ بالا به انتخاب تابع پتانسیل formula_22 بستگی دارد. توابع پتانسیل متفاوت ممکن است به هزینه‌های سرشکن شده متفاوت که همچنان حدود بالا برای هزینه‌های واقعی اند منجر گردند. اغلب در انتخاب یک تابع پتانسیل مبادلاتی می‌توانند انجام گیرند؛ بهترین تابع پتانسیل جهت استفاده بستگی به حدود زمانی مطلوب دارد.بهتر است که تابع پتانسیل:تابع پتانسیلی که در این روش در نظر گرفته می‌شود معادل با تفاوت تعداد ۰ و ۱ ها در هر مرحله می‌باشد. (formula_41 معادل با تعداد بیت‌های تغییر یافته از ۰ به ۱ و بالعکس می‌باشد)formula_23formula_43formula_44در نتیجهformula_45مثال ها.آرایه پویا.یک آرایه پویا را در نظر بگیرید که با افزودن عناصر بیشتر به آن ، اندازه‌ی این آرایه بیشتر میشود، مثل ArrayList در جاوا و std::vector در ++C. به طور مثال اگر از آرایه‌ای به اندازه‌ی ۴ شروع کنیم، می‌توانیم این ۴ عنصر را به آن اضافه کنیم و هرکدام از این عملیات یک دارد. با این حال اضافه کردن عنصر پنجم به این آرایه زمان بیشتری می‌برد به دلیل آنکه باید یک آرایه‌ی جدید که اندازه‌ی آن ۲ برابر آرایه‌ی فعلی (۸) است بسازد، حال عناصر قدیمی را در یک آرایه‌ی جدید کپی کنید و سپس عنصر جدید را اضافه کنید. سه عملیات بعدی اضافه کردن نیز به طور مشابه زمان ثابت می‌برد. سپس افزودن مقدار بعدی نیازمند دو برابر شدن آرایه است که سرعت این عمل بسیار کند است. اگر به طور کلی در یک آرایه‌ی به اندازه‌ی "n" تعداد دلخواه اضافه کردن ها را "n" + 1 نظر بگیریم، ما متوجه می‌شویم که اضافه کردن این عملیات در یک زمان ثابت انجام می‌شود به جز آخری که formula_46 طول می‌کشد. از آنجا که در کل "n" + 1 عملیات وجود دارد می‌توانیم از میانگین آن استفاده کنیم و در یابیم که اضافه کردن عناصر بر روی یک آرایه پویا formula_47 طول می‌کشد، در زمان ثابت.تحلیل شمارندهٔ دودویی.ادعا: به صورت سرشکن در هر مرحله (O(1 رقم تغییر می‌کند. حداکثر تلاش اول برای تعداد ۱ های سمت راست = k +1 - Δ(ϕ) طبق فرمول تابع پتانسیلتحلیل سرشکن شده در درج درخت قرمز سیاه.بگذارید با استفاده از روش تابع پتانسیل در مورد سرشکنی درج درخت قرمز سیاه بحث کنیم:ابتدا ما یک تابع formula_48 تعریف می‌کنیم که مقدار واقعی غیرمنفی یک داده ساختار را به ما می‌دهد که نتیجه‌ی این عملیات می‌تواند باعث تغییر مقدار این تابع پتانسیل شود.در عکس زیر مقدار تابع پتانسیل formula_48 را تعریف می‌کنیم:در تصویر بالا n تعداد رئوس درخت قرمز-سیاه می‌باشد.تابع پتانسیل کل رئوس این درخت قرمز-سیاه formula_50 است.و همچنین : هزینه‌ی سرشکنی = c+Δϕ(h)که طبق تابع پتانسیل (Δϕ(h برابر است با (h’) – formula_48(h)formula_48 و c نیز هزینه‌ی سرشکن ما می‌باشد.تغییر تابع پتانسیل باید به گونه‌ای باشد که برای عملیات کم هزینه مثبت و برای عملیات پر هزینه منفی باشد.رأس جدیدی که در یکی از عضو های درخت قرمز-سیاه درج می‌شود یکی از انواع زیر را دارد:درج و تحلیل سرشکنی در شکل زیر نشان داده شده‌است:این درج ابتدا از تغییر رنگ والدین (قرمز) شروع می‌کند و بچه ها را هم قرمز می‌کند و سپس به سراغ پدربزرگ و عموی همان عضو را رنگ می‌کند که دو حالت پیش می‌آید:۱- جد آن برگ قرمز است.۲- عمو و جد یک عضو هر دو سیاه باشند.( که ممکن است عموی آن عضو قرمز و جدش سیاه است و یا بالعکس)این موضوع در شکل زیر نیز مشخص است:در این درج، رأس بدون هیچگونه تغییری درج می‌شود زیرا عمق درخت یکسان است این در شرایطی است که عضو ما ممکن است خواهر و برادر سیاه داشته باشد و یا اصلا خواهر و برادری نداشته باشد.در نتیجه هزینه‌ی سرشکن شده در این درج 0 می‌باشد.در این درج ما نمی‌توانیم عضو رأسی را تغییر رنگ دهیم زیرا اگر والد و خواهر و برادرش سیاه باشند، سیاه می‌مانند در نتیجه ما باید درخت را به چپ چرخش دهیم.بعد از چرخش همانند شکل زیر برای پر رأسی همانند رأس g اتفاقی نیافتاده و این رأس که سیاه بوده، سیاه باقی مانده و برای جد رأس g نیز که قرمز است باز تغییری صورت نگرفته و این رأس قرمز باقی می‌ماند.در نتیجه هزینه‌ی سرشکن شده‌ی آن طبق شکل زیر ۲+ می‌باشد.بعد از محاسبه کردن این موارد خاص برای محاسبه کردن هزینه‌ی تحلیل سرشکنی حال می‌توانیم درباره‌ی هزینه‌ی سرشکنی آن در حالت کلی بحث کنیم.در صورتی که بدانیم n تعداد کل رئوس ماست داریم: formula_53در نتیجه هزینه کل سرشکن شده در درخت قرمز-سیاه برابر (O(n می‌باشد.منابع.کتاب CLRShttps://en.wikipedia.org/wiki/Amortized_analysis#cite_note-fiebrink-2https://en.wikipedia.org/wiki/Data_structurehttp://en.wikipedia.org/wiki/Accounting_methodhttp://en.wikipedia.org/wiki/Amortized_analysishttp://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s03/www/amortized-analysis.txthttps://web.archive.org/web/20081220170554/http://www.academic.marist.edu/~jzbv/ads/AmortizedAnalysis.htmBerkeley Lecture 35: Amortized AnalysisMIT Lecture 13: Amortized Algorithms, Table Doubling, Potential Method http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec20-amortized/amortized.htm