سلام و وقت بخیر ...
بله به روش درهم سازی به صورت $Binary\: Hash\: Map\:$ در زمان خطی میتوان به این سوال پاسخ داد ، دقت کنیم که در این روش ابتدا باید عنصر $x$ را با مرتبه خطی یافت و سپس عملیات را انجام داد .

یک توضیح کوتاه در مورد $Binary\: Hash\: Map\:$ این ایده که در متن کتاب CLRS ذکر شده به این شکل است که ابتدا یک آرایه $Boolean$ ( ما فرض میکنیم ۰ و یک ها ) ایجاد میکنیم و برای هر عنصر مانند $y$ در آرایه مقدار $BinaryMap[y]$ را یک میکنیم و در انتهای باقی مدخل ها را صفر در نظر میگیریم . ( هندلینگ طول آرایه مهم است )

---

مرسی که سوال داده الگوریتم میذارید. ادم با ایده های بقیه هم اشنا میشه.....

---

(۲۶ فروردین ۱۳۹۶ ۰۵:۴۷ ب.ظ)alireza01 نوشته شده توسط:  سلام و وقت بخیر ...
بله به روش درهم سازی به صورت $Binary\: Hash\: Map\:$ در زمان خطی میتوان به این سوال پاسخ داد ، دقت کنیم که در این روش ابتدا باید عنصر $x$ را با مرتبه خطی یافت و سپس عملیات را انجام داد .

یک توضیح کوتاه در مورد $Binary\: Hash\: Map\:$ این ایده که در متن کتاب CLRS ذکر شده به این شکل است که ابتدا یک آرایه $Boolean$ ( ما فرض میکنیم ۰ و یک ها ) ایجاد میکنیم و برای هر عنصر مانند $y$ در آرایه مقدار $BinaryMap[y]$ را یک میکنیم و در انتهای باقی مدخل ها را صفر در نظر میگیریم . ( هندلینگ طول آرایه مهم است )

اگه میشه این نوع هشو بیشتر توضیح بدید...

اختیار دارید
مرسی از شما دوستان گرامی که همیشه کمک و راهنما هستید
موفق باشید

اهان چون بازه مشخص نکرده نمیشه با شمارشی و سطلی و اینا رفت مجبوریم بعد از پارتیشن و افراز ،با مرتب سازی معمولی سورت کنیم.....
اون هشیم که من گفتم نمیشه رفت چون اون راه مرتبش واسه میانگین مرتبه زمانی میشه تتای n درعیر اینصورت میشه تتای n2.

خوب اگه توی سوال قید نشه، منظورش میانگین هست فکر کنم. برای بهترین حالت یا بد ترین حالت قید می کنن توی سوال

(۲۶ فروردین ۱۳۹۶ ۰۶:۵۳ ب.ظ)alimamala نوشته شده توسط:  خوب اگه توی سوال قید نشه، منظورش میانگین هست فکر کنم. برای بهترین حالت یا بد ترین حالت قید می کنن توی سوال

نه اگه قید نشه منظورش بدترین حالت هست....اگه میانگین بخوان قید میکنن....
اگه روش اقای علیرضا درست باشه ،جواب این سوال غلط میشه.....
چرا من این سوالو تو پوران پیدا نمیکنم؟!

(۲۶ فروردین ۱۳۹۶ ۰۶:۵۵ ب.ظ)*tarannom* نوشته شده توسط:  

(26 فروردین ۱۳۹۶ ۰۶:۵۳ ب.ظ)alimamala نوشته شده توسط:  خوب اگه توی سوال قید نشه، منظورش میانگین هست فکر کنم. برای بهترین حالت یا بد ترین حالت قید می کنن توی سوال

نه اگه قید نشه منظورش بدترین حالت هست....اگه میانگین بخوان قید میکنن....
اگه روش اقای علیرضا درست باشه ،جواب این سوال غلط میشه.....
چرا من این سوالو تو پوران پیدا نمیکنم؟!

سلام . این روش حل به ایده Partition در مورد مرتب سازی سریع اشاره میکنه که عناصر کوچکتر از x رو در مرتبه خطی پیدا میکنه و اونا رو مرتب میکنه ، خوب بدترین حالت اینه که n-1 عنصر کوچکتر از x باشند و برای مرتب سازی اونا به $(n-1)\log(n-1)=O(nlogn)$ هزینه نیاز داریم و اکنون به روش جستجوی باینری میتوان این دو عدد رو یافت .. ( گزینه ۳ ) روشی که بنده گفتم در صورتیی که مجاز به درهم سازی باشیم کاربرد دارد و همچنین بازه اعداد داده شده محدود باشه ( فضا مهم نباشه ) ( البته میشه با یک تابع ابتکار مناسب و نگاشت های هوشمندانه این مساله رو هندلینگ کرد )