۰
subtitle
ارسال: #۱
  
درخواست حل تست IT_87
با سلام
دوستان لطفا این سوالو لطفا برام توضیح بدین
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
دوستان لطفا این سوالو لطفا برام توضیح بدین
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
۰
ارسال: #۲
  
RE: درخواست حل تست IT_87
سلام
با توجه به اینکه حرف از تابع پتانسیل شده پس هزینه ی که سوال میخواد هزینه ی استهلاکی است. در انالیز استهلاکی فرض می شود 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] پس به طور متوسط هزینه ی هر عمل حذف از صف هزینه ی ۳ دارد.گزینه ۳
با توجه به اینکه حرف از تابع پتانسیل شده پس هزینه ی که سوال میخواد هزینه ی استهلاکی است. در انالیز استهلاکی فرض می شود 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] پس به طور متوسط هزینه ی هر عمل حذف از صف هزینه ی ۳ دارد.گزینه ۳
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
درخواست حل تست - احتمالات | ۴۴۰۰۰۰ | ۲ | ۲,۰۴۸ |
۱۱ اسفند ۱۴۰۲ ۰۴:۳۶ ب.ظ آخرین ارسال: حمیدسام |
|
درخواست فیلم نکته تست نظریه دکتر کارگهی | juyaye danesh | ۰ | ۲,۰۳۴ |
۲۵ تیر ۱۳۹۹ ۰۱:۰۸ ب.ظ آخرین ارسال: juyaye danesh |
|
درخواست حل تست - فلیپ فلاپ JK | ۴۴۰۰۰۰ | ۱ | ۲,۷۰۳ |
۲۰ مرداد ۱۳۹۷ ۰۹:۳۳ ب.ظ آخرین ارسال: erfan30 |
|
درخواست حل تست - سری دو | ۴۴۰۰۰۰ | ۵ | ۴,۵۰۹ |
۱۷ دى ۱۳۹۶ ۰۲:۵۱ ق.ظ آخرین ارسال: hamed chidan |
|
درخواست حل تست - سری یک | ۴۴۰۰۰۰ | ۳ | ۳,۴۸۸ |
۱۳ شهریور ۱۳۹۶ ۰۹:۳۹ ب.ظ آخرین ارسال: hamed chidan |
|
درخواست حل تست - هاب | ۴۴۰۰۰۰ | ۱ | ۲,۹۹۱ |
۰۹ شهریور ۱۳۹۶ ۰۹:۱۷ ب.ظ آخرین ارسال: Saman |
|
درخواست حل تست - اشتراک فایل در یونیکس | ۴۴۰۰۰۰ | ۱ | ۲,۳۶۹ |
۰۹ شهریور ۱۳۹۶ ۰۹:۰۴ ب.ظ آخرین ارسال: Saman |
|
درخواست حل تست - DNS Client | ۴۴۰۰۰۰ | ۰ | ۱,۵۳۴ |
۳۰ مرداد ۱۳۹۶ ۱۱:۴۳ ق.ظ آخرین ارسال: ۴۴۰۰۰۰ |
|
درخواست حل تست - فایروال | ۴۴۰۰۰۰ | ۰ | ۱,۴۲۳ |
۳۰ مرداد ۱۳۹۶ ۱۱:۴۲ ق.ظ آخرین ارسال: ۴۴۰۰۰۰ |
|
درخواست حل تست - پردازش برداری | ۴۴۰۰۰۰ | ۰ | ۱,۳۰۲ |
۳۰ مرداد ۱۳۹۶ ۱۱:۳۶ ق.ظ آخرین ارسال: ۴۴۰۰۰۰ |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close