دوستان فک می کنم سوال ۱۸ میشد گزینه ۲ یعنی logn. چون حلقه اول که یک عدد ثابته. حلقه دوم به دلیل j=j*2 تا logn پیش میره. حلقه سوم هم که هربار با شرط درست شروع میکنه، اما به محض اجرا b=0 میشه و میاد بیرون.
ضمنا منم جواب سوال ۱۹ رو ۲۶ آوردم. (گزینه۲)
سوال ۲۰ رو هم زدم n2، فک میکنم در حالت عادی، پیچیدگی نمایی بشه (۲ به توان n منهای یک)، ولی به کمک روش پویا و استفاده از یک ماتریس میشه n2.
تحلیلم درسته یا نه ؟
(۰۸ اسفند ۱۳۹۵ ۰۱:۴۰ ق.ظ)computerman نوشته شده توسط: اقای mahditorki منم موافقم با نظرتون راجب به سوال ۳
چون از O استقاده کرده و O یعنی همه حالت یه الگوریتم حداکثر به این پیچیدگی برسن و به نطر من هم O)nمیشهنا
راس میگینا
برای سوال ۲ که هر دو گزینه ۳ و ۴ درسته ک
به نظرم روی کلید اولیه اومد اعتراض کنیم ممکنه به خاطر کلمه "بهترین" بگن نه هر دوش امکان پذیر نیست؟
درمورد سوال ۳ تحلیل بنده این بود که هروقت در سوال به "بدترین حالت" اشاره نشده، منظور سوال همون حالت "میانگین" هستش. اما تحلیل شما و سایر دوستان هم قابل توجه هستش که نماد O یعنی پوشش همه حالات!
در مورد سوال ۲، به نظرم گزینه۴ درسته. چون همونطور که میدونیم، حذف از هیپ به ارتفاع هیپ (logn) بستگی داره، برای پیداکردن kامین مینیمم، باید kبار حذف ریشه از هیپ انجام بشه که پیچیدگی اون klogn خواهد بود. اما یه راه حل ساده تر هم هست:
بیایم یک هیپ جدید بسازیم، ریشه هیپ قبلی رو در هیپ جدید کپی و درج کنیم (دقت کنید گفتم کپی از هیپ قبلی که دیگه مجبور نشیم این هیپ قبلی رو هربار heapify کنیم). حالا kبار از این هیپ جدید، ریشه رو حذف کنیم و هربار فرزندان این گره حذف شده رو از هیپ قدیم در هیپ جدید درج کنیم. kامین حذف ریشه به معنی kامین مینیمم هستش.
(فلسفه این روش اینه که ارتفاع درخت بجای logn میشه logk، درنتیجه kبار حذف ریشه از این هیپ، برامون هزینه klogk داره و چون درخت ارتفاع کمتری داره و درج و حذف از اون به صرفه تره)
درمورد سوالات عمومی هم بگم بنده سال گذشته به صورت دورهمی شرکت کردم، ۳۳درصد هوش زدم (به سوالات زبان نرسیدم). اما امسال فقط ۸ سوال اول رو که در مورد تحلیل متن بود، تونستم جواب بدم. احتمالا سه حالت داره:
۱- یا هوش بنده نسبت به پارسال کم شده!
۲- یا سوالات سخت تر شده بود!
۳- یا اینکه برعکس پارسال که موقع جواب دادن به سوالات تخصصی بیخیال و راحت بودم، امسال فشار زیادی بهم اومده و واسه سوالات هوش قند خون کم آوردم.
