سلام دوستان
می خواستم بدونم که آیا تحلیل سرشکن جزو سرفصل های کنکور هست؟ آیا تا بحال تستی تو کنکور ازش اومده؟ (مستقیم یا غیر مستقیم)
من تو هیچ کتاب کنکوری، مطلبی پیدا نکردم که درباره تحلیل سرشکن باشه، از رو CLRS هم خوندمش ولی یه مقدار یه جوریه!!! آخراش رو هم دیگه کلا نفهمیدم!
مرسی بابت راهنمایی
فکر کنم بیاد اما به طور مستقیم به اسم "تحلیل سرشکنی" اشاره نمیشه
پس به چه اسمی اشاره میشه؟
چه تیپی سوال میاد؟
آیا تا حالا سوال اومده؟
(۲۶ تیر ۱۳۹۱ ۱۱:۲۹ ب.ظ)MSZ نوشته شده توسط: پس به چه اسمی اشاره میشه؟
چه تیپی سوال میاد؟
آیا تا حالا سوال اومده؟
فکر کنم اولین تست ۹۰ نرم افزار همین تحلیل سرشکنی بود .
مطلب خیلی خاصی نیست و ۲ - ۳ تا روش کوچولو داره ، یه نگاه بهش بندازین ، تست ۹۰ هم جزء ۲ - ۳ مثال کتاب کرمن بود .
فقط یکی دو بار ازش سئوال دادن شایدم از دستشون در رفته اخه جز مباحث کارشناسی نیستش
اره به این اسم نمیدن
مباحث این بحث هم به این صورته هست که فرض کنید یه ساختمان داده داریم (مثل پشته) و به طبع یک سری عملیات روی ساختمان داده مورد نظر (pop و push و ...) حالا مسئله اینه که هزینه هر عملیات به تنهایی (مثلا pop )به ازای یک توالی از n عملیات بروی ساختمان داده مورد نظر چقدر است . که سه روش عنوان میشه اما در کنکور چندان پیچیدش نمیکنن و همین که درک کنی مسئله ازت چی میخواد میتونی حل کنی .
در واقع اسمش روش هست : تحلیل سرشکن : یعنی ما به دنبال هزینه کل برای n تا عمل نیستیم بلکه به دنبال سرشکن کردن این هزینه کل بر روی عملیاتها و به طبع هزینه هر عمل خاص به ازای این n عمل هستیم .
(((تو پرانتز به عنوان اول راه حل که مطرح میشه واسمش رو هم میزارن تحلیل جمعی به این صورته که اگر فرض کنید یک توالی از n عمل در مجموع , زمان [tex]T(n)[/tex] vm رو صرف میکنه بنابراین در بدترین حالت هر عمل به تنهایی (مثلا pop ) برای اجرا به هزینه [tex]\frac{T(n)}{n}[/tex] نیاز داره و این همان میانگین خودمون هستش و در واقع و به ذهن هر کسی در وهله اول میرسه . البته همه چیز به همین سادگی هم نیست و این روش هم نقاط ضعف خودش رو داره و چندان هم واقعی نیست مثلا در ارتباط با ساختمان داده لیست به نظر شما ایا هزینه درج در ابتدای لیست (۱)Oبا حذف یکسان است(اول باید لیست رو جستجو و بعد انرا حذف کنیم) و هزینه این عمل ها به یک نسبت در هزینه کل تاثیر میزاره!!! )))
توصیه :
به نظر من زیاد گیر به این بحث و چنتا بحث دیگه(مثل تحلیل احتمالی) در کتاب CLRS نکن چون اولا ممکنه در برخورد اول برات گنگ باشه و یه نموره رو اعصابت راه بره
اما هیچی نیست اگر مفهومش رو درک کنی و اگر هم خیلی ادم سمجی هستی مثل من
که گیر میده به مبحث به نظرم تست هاش رو حل کن و باز وقتت رو با خوندن متن تلف نکن چون با حل تست دستت میاد چیکار باید بکنی .من تست کنکورش الان در ذهنم نیست اما فکر کنم در مورد پشته بود اگر دیدی هنوز هم مشکل داری بگو تا دور همی یه نمونه اش رو حل کنیم
سال ۸۹ تخصصی نرم داده بودند یکی از تمرینهای فصل ۱۷ از clrs بود