(۰۵ مهر ۱۳۹۴ ۱۰:۲۲ ب.ظ)iCanDoIt نوشته شده توسط:  سلام دوستان.
من فصل سوم کتاب پوران رو دارم می خونم به یه بخشی رسیدم با عنوان آنالیز استهلاکی و تجمعی.
حقیقتش هر چی می خونمش هیچ چی نمی فهمم اگه کسی می دونه و یه توضیحی بیاد در موردش بده ممنونش میشم.
همچنین روش حسابرسی و پتانسیل چی می خواد بگه؟

با تشکر.

سلام عزیز مشکلتون چیه بفرمایین بعدش چشم
اتفاقا معمولا یه سوال ازش میاد دقت بفرمایین انالیز استهلاکی وانالیز حالت میانگین باهم فرق دارن و این نکته رو دکتر سی جوادی توی تست ۹۲ اشتباه حل کرده

(۰۵ مهر ۱۳۹۴ ۱۰:۲۲ ب.ظ)iCanDoIt نوشته شده توسط:  سلام دوستان.
من فصل سوم کتاب پوران رو دارم می خونم به یه بخشی رسیدم با عنوان آنالیز استهلاکی و تجمعی.
حقیقتش هر چی می خونمش هیچ چی نمی فهمم اگه کسی می دونه و یه توضیحی بیاد در موردش بده ممنونش میشم.
همچنین روش حسابرسی و پتانسیل چی می خواد بگه؟

با تشکر.

سلام
این یکی از مهمترین قسمت های ساختمان داده هست که هر سال توی کنکور سوال میاد و معمولا یکی از سوالایی هست که کمتر کسی جواب میده ولی حل کردنش خیلی سخت نیست. من پیشنهاد می کنم که یا قسمت سرشکنی کتاب داده ساختار دکتر قدسی یا قسمت Amortized کتاب CLRS رو مطالعه کنید.

سه روش محاسبه هست ۱- آنالیز تجمعی ۲- روش حسابرسی ۳- روش پتانسیل
دو مسئله کلاسیک وجود دارد ۱-مولتی پاپ ۲- شمارنده دودویی
که در این منابع این دو تا مسئله رو با هرسه مدل محاسبه کرده. هر مسئله ای رو با هر روشی میشه حل کرد اما هر مسئله با یک روش بهتر قابل حله.
امکان توضیح جامع در این جا وجود ندارد و پیشنهاد می کنم حتما این قسمت رو بخونید اگر سوالی بود بپرسید.

سلام.

آنالیز استهلاکی زمان اجرای متوسط هر عمل در بدترین حالت را نشان می دهد. در این آنالیز N عمل انجام می شود و هزینه زمانی این عملیات رو N عمل سرشکن می شود. این یعنی چی ؟ یه مثال می زنید؟

آنالیز تحمعی که راحت تره: هزینه N عمل را به دست می آوریم سپس به N تقسیم می کنیم.

توضیح داده شده توسط
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
:
فرض کنید n تا عمل (operation) داریم و زمان اجرای بدترین حالت برای این n عمل را T(n) بنامید. درینصورت هزینه سرشکن تجمعی این n عمل میشود T(n)/n. یعنی زمان اجرای بدترین حالت را بر تعداد کل عملها تقسیم میکنیم.

روش حسابرسی: این چی میخواد بگه؟ لطفا مثال بزنید.

روش پتانسیل: اینم خیلی گنگه لطفا مثال بزنید.

با تشکر