موضوع مقاله: تحلیل سرشکنی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تحلیل سرشکنی | مقدمه: تحلیل سرشکنی در علوم کامپیوتر به خصوص در تحلیل الگوریتم‌ها، تحلیل سرشکنی زمان اجرای میانگین برای هر دستور را در بدترین حالت بدست می‌آورد. | ## بخش 1: تحلیل سرشکنی | تحلیل سرشکنی با متوسط زمان اجرا تفاوت دارد چرا که زمان اجرای هر دستور در بدترین حالت را بیان می‌کند. برای این کار، گاهی پیشنهاد می‌شود که به‌طور مستقیم بدترین زمان اجرا را بدست آوریم. اما تحلیل سرشکنی این امکان را به ما می‌دهد تا زمان اجرایی بسیار نزدیک به زمان اجرای واقعی بدست آوریم. شبه کد تحلیل سرشکنی اینجا هدف این است که هزینه‌ی یک عمل را بدون توجه به ورودی به دست بیاوریم. این روش (تحلیل سرشکنی) در واقع: میانگین اجرای هر عمل در بدترین حالت را بدست می‌ آورد. این تحلیل این‌گونه تفسیر می‌شود که بعضی از دستورهای پر هزینه در آینده برای دستورهایی که هزینه‌ی کمتری دارند خرج شود. تاریخچه تحلیل سرشکن شده در ابتدا از روشی به نام تحلیل متراکم پدید آمده که امروزه شامل تحلیل سر شکن است. این تکنیک بار اول توسط رابرت تارجان در مقاله پیچیدگی محاسباتی وقف شده‌اش در سال ۱۹۸۵ معرفی شد. که نیاز به یک شکل مفیدتر از تحلیل روشهای احتمالی متداول مورد استفاده را برطرف می کند. سرشکنی در ابتدا برای انواع خاصی از الگوریتم‌ها مورد استفاده قرار می گرفت، به ویژه آنهایی که مربوط به درختان باینری و عملیات یونیون هستند. با این حال، امروزه هم از این تحلیل کاربرد های زیادی دارد و هنگام تحلیل بسیاری از الگوریتم های دیگر نیز مورد استفاده قرار می گیرد. روش انبوهه در روش انبوه ابتدا باید هزینه‌ی پی در پی اجرای n عملیات را محاسبه کنیم که در کل هزینه‌ی آن دنباله‌ای از n عملیات است و زمان اجرای آن است و سپس آن را بر تعداد (n) تقسیم کرده و در نتیجه هزینهٔ میانگین یا سرشکن شده که برابر T(n) / n است برای هر عمل بدست می‌آید. برای تحلیل شمارنده با این روش این‌گونه در نظر گرفته می‌شود که اگر تغییر بیت‌های در هر مرحله را در نظر بگیریم در مجموع برابر با ۲n و در نتیجه زمان اجرای آن می‌شود. روش حسابداری روش حسابداری نوعی از تحلیل انبوه است که به هر عمل یک هزینه‌ی سرشکن شده اختصاص میابد که ممکن است با هزینه‌ی واقعی متفاوت باشد. در این روش در ابتدا یک سری عملیات ابتدایی که در الگوریتم مورد استفاده قرار می‌گیرند را انتخاب می‌کنیم و به صورت دلخواه هزینه‌ی آن‌ها را ۱ در نظر می‌گیریم. به هر مجموعه عملیات یک هزینه نسبت داده می‌شود و عملیاتی که هزینه‌ی کمتری دارند پولشان برای هزینه‌های بعدی ذخیره می‌شود. | ## بخش 2: تحلیل سرشکنی | برای این داده ساختار به ازای هر عمل ۲ریال هزینه می‌کنیم که این ۲ریال صرف تغییر ۰ به ۱ و بالعکس می‌شود. به صورت کلی هنگامی که هزینه سرشکن شده یک عمل از هزینه واقعی آن تجاوز کند، اختلاف این هزینه به عنوان موجودی به اشیایی مشخص در ساختمان داده اختصاص می‌یابد. موجودی بعداً می‌تواند در جهت کمک به پرداخت برای اعمالی که هزینه سرشکن شده آنها کمتر از هزینه واقعی شان است مورد استفاده قرار گیرد. بنابراین می‌توان هزینه سرشکن شده یک عمل را مشاهده کرد که بین هزینه واقعی آن و موجودی که پرداخت شده یا استفاده می‌شود، تقسیم شده‌است. این روش با تحلیل جمعی که در آن تمام اعمال هزینه‌های سرشکن شده یکسانی دارند، بسیار متفاوت است. اگر بخواهیم تحلیل را با هزینه‌های سرشکن شده انجام دهیم تا نشان دهیم که در بدترین حالت هزینه میانگین هر عمل کم است، کل هزینه سرشکن شده یک توالی از اعمال باید یک حد بالا برای هزینه کل واقعی توالی باشد. علاوه بر این همانند تحلیل جمعی، این رابطه باید برای تمام توالی‌های اعمال برقرار باشد. اگر هزینه واقعی امین عمل را با و هزینه سرشکن شده امین عمل را با نشان دهیم، برای تمام توالی‌هایی از عمل داریم: بنا به نامساوی بالا کل موجودی مربوط به ساختمان داده باید در همه زمان‌ها نامنفی باشد. اگر کل موجودی می‌توانست منفی باشد(در نتیجه پرداخت ارزش کم به عمل‌های قبلی، با این تعهد که دوباره پس از آن پرداخت صورت گیرد) آنگاه کل هزینه‌های سرشکن شده ایجاد شده در آن هنگام کمتر از کل هزینه‌های واقعی ایجاد شده می‌بود؛ برای توالی عمل‌ها تا آن زمان کل هزینه سرشکن شده یک حد بالا برای کل هزینه واقعی نمی‌بود. هزینه‌ی سرشکن: هزینه‌ای که در آینده، بقیه عمل ها روی این عمل شارژ می‌شوند + هزینه‌ای که روی بقیه شارژ می‌کنیم - هزینه‌ی واقعی روش تابع پتانسیل روش تابع پتانسیل نوعی از روش حسابداری است که در آن اعتبار ذخیره شده به عنوان تابعی از وضعیت داده ساختار محاسبه می‌شود. در این روش به داده ساختار داده شده یک تابع پتانسیل نسبت می‌دهیم و با یک ساختمان داده اولیه را شروع می‌کنیم که روی آن عمل انجام می‌شود. برای هر ، را هزینه واقعی امین عمل قرار می‌دهیم و را ساختمان داده‌ای که پس از به کارگیری امین عمل روی ساختمان داده حاصل می‌شود، قرار می‌دهیم. هزینه سر شکن شده مربوط به امین عمل با توجه به تابع پتانسیل به صورت زیر تعریف می‌شود: براین هزینه سرشکن شده هرعمل برابرهزینه واقعی آن به علاوه افزایش پتانسیل حاصل از عمل می‌باشد. بنا به معادله بالا، هزینه سرشکن شده کل عمل برابر است با: اگر بتوانیم یک تابع پتانسیل تعریف کنیم بطوریکه ، آنگاه هزینه سرشکن شده کل ، یک حد بالا برای هزینه واقعی کل می‌باشد. بنابراین اگر برای تمام ها تأکید کنیم که، آنگاه همانند روش حسابداری تضمین می‌کنیم که از پیش هزینه را پرداخت کرده‌ایم. به‌طور شهودی اگر اختلاف پتانسیل از امین عمل مثبت باشد آنگاه هزینه سرشکن شده یک پرداخت اضافه به امین عمل را نشان می‌دهد، و پتانسیل ساختمان داده افزایش می‌یابد. | ## بخش 3: تحلیل سرشکنی | اگر اختلاف پتانسیل منفی باشد، آنگاه هزینه سرشکن شده، یک پرداخت کم به امین عمل را نشان می‌دهد و هزینه واقعی عمل با کاهش پتانسیل پرداخت می‌شود. هزینه‌های سر شکن شده تعریف شده به وسیله دو معادلهٔ بالا به انتخاب تابع پتانسیل بستگی دارد. توابع پتانسیل متفاوت ممکن است به هزینه‌های سرشکن شده متفاوت که همچنان حدود بالا برای هزینه‌های واقعی اند منجر گردند. اغلب در انتخاب یک تابع پتانسیل مبادلاتی می‌توانند انجام گیرند؛ بهترین تابع پتانسیل جهت استفاده بستگی به حدود زمانی مطلوب دارد. تابع پتانسیلی که در این روش در نظر گرفته می‌شود معادل با تفاوت تعداد ۰ و ۱ ها در هر مرحله می‌باشد. به طور مثال اگر از آرایه‌ای به اندازه‌ی ۴ شروع کنیم، می‌توانیم این ۴ عنصر را به آن اضافه کنیم و هرکدام از این عملیات یک زمان ثابت دارد. با این حال اضافه کردن عنصر پنجم به این آرایه زمان بیشتری می‌برد به دلیل آنکه باید یک آرایه‌ی جدید که اندازه‌ی آن ۲ برابر آرایه‌ی فعلی (۸) است بسازد، حال عناصر قدیمی را در یک آرایه‌ی جدید کپی کنید و سپس عنصر جدید را اضافه کنید. سپس افزودن مقدار بعدی نیازمند دو برابر شدن آرایه است که سرعت این عمل بسیار کند است. اگر به طور کلی در یک آرایه‌ی به اندازه‌ی n تعداد دلخواه اضافه کردن ها را n + 1 نظر بگیریم، ما متوجه می‌شویم که اضافه کردن این عملیات در یک زمان ثابت انجام می‌شود به جز آخری که طول می‌کشد. از آنجا که در کل n + 1 عملیات وجود دارد می‌توانیم از میانگین آن استفاده کنیم و در یابیم که اضافه کردن عناصر بر روی یک آرایه پویا طول می‌کشد، در زمان ثابت. حداکثر تلاش اول برای تعداد ۱ های سمت راست = k +1 - Δ(ϕ) طبق فرمول تابع پتانسیل Q۳ Q۲ Q۱ Q۰ ۰ ۰ ۰ ۰ ۰ ۰ ۰ ۱ ۰ ۰ ۱ ۰ ۰ ۱ ۱ ۱ ۱ ۰ ۰ ۰ تحلیل سرشکن شده در درج درخت قرمز سیاه بگذارید با استفاده از روش تابع پتانسیل در مورد سرشکنی درج درخت قرمز سیاه بحث کنیم: ابتدا ما یک تابع تعریف می‌کنیم که مقدار واقعی غیرمنفی یک داده ساختار را به ما می‌دهد که نتیجه‌ی این عملیات می‌تواند باعث تغییر مقدار این تابع پتانسیل شود. و همچنین : هزینه‌ی سرشکنی = c+Δϕ(h) که طبق تابع پتانسیل (Δϕ(h برابر است با (h’) – (h) و c نیز هزینه‌ی سرشکن ما می‌باشد. تغییر تابع پتانسیل باید به گونه‌ای باشد که برای عملیات کم هزینه مثبت و برای عملیات پر هزینه منفی باشد. بعد از چرخش همانند شکل زیر برای پر رأسی همانند رأس g اتفاقی نیافتاده و این رأس که سیاه بوده، سیاه باقی مانده و برای جد رأس g نیز که قرمز است باز تغییری صورت نگرفته و این رأس قرمز باقی می‌ماند. | ## جمع‌بندی | در صورتی که بدانیم n تعداد کل رئوس ماست داریم: در نتیجه هزینه کل سرشکن شده در درخت قرمز-سیاه برابر (O(n می‌باشد.