on یکم مشکوکه. من نتونستم چیزی با این مرتبه به دست بیارم. چون گفته با هزینه مصرفی ثابت. اگه نمی گفت میشد به دست بیارین. nolgn که مشخصه میشه با مرتب سازی و بعدش پیدا کردن این عنصر با هزینه مصرفی ثابت
یه سوال کی میشه از هش استفاده کرد؟ اگه بگن یا نه و مرتبه اش به طور متوسط چقدره؟

من به نظرم اینجوریه که میایم تو o(n) آرایه رو از مکان n/3 پارتیشن میکنیم و از n/3 تا آخر رو هم روی ۲n/3 پارتیشن می کنیم. حالا ما آرایه رو به سه دسته ی مجزا تقسیم کردیم. از ۰ تا n/3 ، از n/3 تا ۲n/3 و از ۲n/3 تا آخر. من معتقدم مقدار مورد نظر ما یا عنصر n/3ام آرایه است یا ۲n/3. واسه اینکه بفهمیم کدومه کافیه تعداد اونهارو تو دسته های مجاورشون بشمریم و بینیم که بیشتر ار n/3 هست یا نه که مجموعه ی این کارا توی o)n) انجام میشه.
در مورد این که چرا مطمئنم می تونی هر آرایه ی دلخواهی که شرایط مسئله رو داره می خوای بنویسی و بعد مرتبش کنی و آیتم n/3 و ۲n/3 امش رو در نظر بگیری که میشه همون مقداری که از پارتیشن به دست میاد. بعد میبینی که حتما همون عدد جوابه.
دلیل قانع کننده ترش اینه که وقتی از یه عددی بیشتر از n/3 داریم و هر دسته هم n/3 تا ظرفیت داره حتما این عدد تو ۲ تا دسته حضور داره و این امکان نداره بعد از پارتیشن یک عدد هم در سمت چپ محور باشه هم سمت راست محور مگر اینکه مقدارش با محور برابر باشه.
خیلی فکر کردم تا این جوابو به دست بیارم. نمی تونم سر کنکور چجوری باید اینو می فهمیدن بیچاره ها

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

روشتو قبول دارم آرمین جان!ولی وقتی می دونیم گزینه ۱ درسته این مدلی تحلیل می کنیم!قبول داری؟!
یعنی بشخصه من اگه سر جلسه این سوالرو ببینم عمرا توی اون وقت با اطمینان بزنم گزینه یک رو!
بهرحال ممنون

(۱۷ بهمن ۱۳۹۱ ۰۵:۳۳ ب.ظ)۸Operation نوشته شده توسط:  روشتو قبول دارم آرمین جان!ولی وقتی می دونیم گزینه ۱ درسته این مدلی تحلیل می کنیم!قبول داری؟!
یعنی بشخصه من اگه سر جلسه این سوالرو ببینم عمرا توی اون وقت با اطمینان بزنم گزینه یک رو!
بهرحال ممنون

به نظر من که اصلا نباید سر همچین سوالایی واسیتاد. باید ردشون کنی و وقتی وقت اضافه داشتی بیای سرشون. بعدشم باید نگاه کنی به گزینه ها. logn که یه جورایی معلومه نمیشه. nlogn هم که راحت میشه واسش جواب پیدا کرد. پس اینجا می مونه n. حالا باید زور بزنی با استفاده از ابزارایی که داری و بلدی یه راه حل پیدا کنی واسش. اگه تونستی میزنی n اگر نتونستی نمی زنی سوالو

عالی

برای این مثال لطفا توضیح بدین
۱۲۳۴۵۶۳۳۳۳۴۴۳۳۵۵۵۵
۱۲۳۴۵۶
۳۳۳۳۴۴
۳۳۵۵۵۵
n=18
جواب سه هست
الآن بیشینه ها رو باید محاسبه کنیم تو هر بخش؟
یکیش که اصلا مشخص نیست بیشینه چیه. بعدیش میشه سه و بعدیش هم میشه پنج

اون طوری که من فهمیدم، با محاسبه بیشینه در هر بخش، حتما یکی از بیشینه ها عدد موردنظر است که استدلال درستی است.
برای مثالی مثل n=18
۳و۲و۳و۴و۲و۴
۵و۳و۵و۳و۱و۱
۳و۸و۳و۸و۳و۸
که جزو سخت ترین مثالهاست کاری که باید بکنیم اول محاسبه بیشینه است در هر بخش.
که میشه ۲و۳و۴ هر کدام دو در بخش اول، ۱و۳و۵ هر کدام دو در بخش دوم و ۳و۸ هر کدام سه در بخش سوم با داشتن تعداد آنها و جمعشان سه عدد موردنظر است.
می توان اثبات کرد که برای نگه داری اطلاعات بیشینه ها به تعداد خانه های ثابت نیاز است