با سلام
دوستان لطفا این سوالو لطفا برام توضیح بدین
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام
با توجه به اینکه حرف از تابع پتانسیل شده پس هزینه ی که سوال میخواد هزینه ی استهلاکی است. در انالیز استهلاکی فرض می شود n عمل انجام شده و هزینه ی کلی این n عمل را بدست می اورند و روی n عمل سرشکن می کنند تا هزینه ی استهلاکی یک عمل بدست اید.در واقع به نوعی یک هزینه ی متوسط هر عمل را در حالتی که هزینه ی عمل ها می تواند متفاوت باشد بدست می اوریم. عملی که در سوال هزینه اش پرسیده شده حذف از جلوی صف است. صفی که با دو پشته پیاده سازی شده طوری که اگر پشته ی [tex]S_2[/tex] خالی نباشد از ان عمل حذف را انجام می دهد که فرض می کنیم دارای هزینه ی یک واحدی است. وگرنه اگر [tex]S_2[/tex] خالی باشد تمام عناطر موجود در [tex]S_1[/tex] ابتدا پاپ شده و به [tex]S_2[/tex] پوش می شود و بعد یک حذف از [tex]S_2[/tex] انجام می شود.معمولا در بدست اوردن هرینه ها بدترین حالت را در نظر می گیرند که در این ساختار فرض می کنیم در پشته ی اول n عنصر وجود دارد ولی پشته ی دوم خالی است پس اگر بخواهیم تمام n عنصر را حذف کنیم یا به عبارتی n عمل حذف از جلوی صف انجام دهیم ابتدا باید n عنصر از پشته ی اول پاپ و به پشته ی دوم پوش شود که ما هزینه ی پاپ و پو ش را هر کدام یک واحد می گیریم پس n عمل پاپ n تا هزینه دارد و n عمل پوش n تا هزینه و در این حالت تمام n عنصر در پشته ی اول قرار گرفت حال برای n عمل حذف کافیه n بار از پشته ی دوم با هزینه ی یک واحد ی برای هر کدام و مجموع n واحدی تمام n عنصر را حذف کنیم در واقع اولین حذف از صف هزینه ی [tex]2n+1[/tex] دارد و[tex]n-1[/tex] حذف دیگر هزینه ی [tex]n-1[/tex] دارد و مجموع [tex]3n[/tex] پس به طور متوسط هزینه ی هر عمل حذف از صف هزینه ی ۳ دارد.گزینه ۳