بررسی یک سوال مرتب سازی

Question

سلام

یک کتاب نسبتا معتبر دارم می خونم سوال زیر رو مطرح کرده و جواب O(nlogn) رو قرار داده :

به یک الگوریتم کارا نیاز داریم تا در یک آرایه به طول n ، عنصری را که K بار تکرار شده است را بدست آورد.دقت کنید که K در ورودی داده شده و مستقل ازn است.زمان اجرای

سریع ترین الگوریتم برای این مسئله چیست ؟

من فکر می کنم با زمان نهایتا خطی بشه با صرف حافظه به جواب رسید ؛ منظور کارا اگر سرعت باشه زمان خطی واگر میزان حافظه باشه همون جواب اصلی

با تشکر

Answer 1

جواب کتاب درسته .

 

چند شکل میشه این الگوریتم رو نوشت :

 

1_ اول مرتب سازی کنیم بعد عناصر پشت سر هم رو بشماریم که میشه n+nlong  عملیات که همون اوردر nlogn هست .

 

2_ یک balance search tree مسازیم با اسم مثلا t

یک بار آرایه رو از اول تا آخر شروع به پیمایش می کنیم بعد تعداد رو داخل t هر بار که یک عنصر دیدیم اضافه می کنیم .

پیمایش اوردر n هست و پیدا کردن logn که میشه nlogn .

 

3_ اگر بجای balanced search tree از hashtable استفاده کنیم اوردر میانگین میشه n ولی worst case میشه n^2

 

4_ اگر داخل آرایه عدد ذخیره شده باشه و  رنج اعداد کوچیک باشه میشه بجای balanced search tree از یک آرایه با سایز بزرگترین عنصر استفاده کرد و هر عنصر رو با ایندکس پیدا کرد که این طوری اوردر میشه n . ولی چون سوال حرفی از عدد بودن نزده این کارو نمیشه کرد .(direct address table )

 

5_ اگر هم از  disjoint set استفاده کنیم اوردر باز هم همون nlogn میشه (البته در حالت میانگین )

Answer 2

ابتدا یک پیمایش به ظول n انجام داده و یک مجموعه به اصطلاح universe می سازیم که مفادیر اولیه آن در همه درایه ها 0 است.

می دونیم که توابع hash table تناظر یک یه یک دارند با مقادیر ورودی تابع.

پس با پیمایشی به طول n و استفاده از تابع مذکور به ازای هر عنصر آرایه تعداد تکرار به صورت یک شمارنده ای شبیه به مرتب سازی شمارشی اون عنصر increment بشه و هر عضو شبه آرایه tag به اون بزنیم که نماینده عنصر اولیه در آرایه ابتدایی است بعد k رو بیابیم

Comments

بالا هم گفتم که با هش تیبل و روش open addressing اوردر بدترین حالت (n^2 )  میشه .
روش direct address  که O(n میشه هم قابل انجام نیست . چون تگ زدن به عضو های غیر integer آرایه  همیشه ممکن نیست .(و صد البته برای تگ زدن هم نیاز به یک جست و جو هم دارید مثلا فرض کنید داخل آرایه این ذخیره شده : a a c b حالا پیمایش که می کنیم برای a تگ 1 رو در نظر می گیریم برای b باید جست وجو کنیم که آیا تا حالا تگ زده شده یا خیر و اگر زده شده دیگه تگ نزنیم که این جست و جو و تگ زدن خودش  nlogn زمان می گیره .)

---

در صورت سوال گفته شده K داده شده !
فرض کنید یک کلاس بنویسیم و یک متعیر local و یک شمارنده برای k اون هم محلی .یک آرایه از اشیا می سازیم از ابتدا شروع به پیمایش به اندازه n می کنیم در هر گام hash function اجرا میشه و به یک عنصر آرایه نگاشت میشه در هنگام نگاشت متغیر local و شمارنده که مقدار 0 داره رو update می کنیم . حال با توجه به مقدار k از ابتدا روی آرایه از اشیا حزکت کرده و هر شی که increment شده ی آن برابر k بود مقدار متغیر شمارنده و local اون رو بر می گردونیم.ما مقایسه ای برای tag زدن نداریم و ممکنه مقدار متعیر local چند بار در o(1) update بشه

---

برای "حالت میانگین" اگر یک hash function یونیفرم داشته باشیم مطلبی که گفتید درسته .
ولی مشکل این جاس که hash function نمی تونه "همیشه" به یک عنصر مجزا اشاره کنه . در بدترین حالت همه ی نگاشت ها به یک محل هستن یعنی باید یک link list رو پیمایش کنیم که (O(n هست .
منظورم از تگ زدن برای جا هایی بود که بخواهیم مستقیم و بدون استفاده از تابع hash   با ایندکس دسترسی پیدا کنیم .
در کل منظور من اینه  با توجه به این که سوال حرفی در مورد تابع هش نزده با مرتبه کمتر از nlogn این کار "همیشه" قابل انجام نیست  و این که نمیشه گفت استفاده از hash table همیشه از sort کردن برای پیدا کردن عنصری که k بار تکرار شده سریع تر هست .

---

فکر می کنم موضوع این تاپیک بد انتخاب شده که ذهنتون در مرتب سازی مشغول هست
در اینجا اتفاقا ما می خواهیم hash function به یک object اشاره کنه  و uniform نباشه  برای مثال از یک hash function به صورت مدولار داشته باشیم اگر چند عنصر تکراری مثلا 4 تا 1 مطمئنا هر چهار تا برای ورودی یک به  یکجا نگاشت می شود و ما همون موقع increment می کنیم . این الگوریتم مبنا کارش بدست آوردن فراوانی داده هاست که صورت سوال دنبال فراوانی k ست.
در اینجا به هیچ عنوان به دنبال مقایسه یا مرتب سازی k یا هر مورد دیگه ای نیستیم.

---

یونیفورم بودن به این معنی نیست که چند تا 1 به محل متفاوتی اشاره کنند چون 1 ها با هم برابر هستن طبیعتا به یک محل نگاشت می کنند .
به این معنیه که مثلا فرض کنید hash table با  n  تا slot داریم "احتمال" این که  یک عنصر جدید بتونه به هر کدوم از slot ها نگاشت بشه کاملا یکسان باشه و به این که قبلا چه عنصری در اون خونه قرار گرفته باشه ربطی نداشته باشه (که با این شرط زمان متوسط جست و جو یک تابع میشه با رشد پایین بر حسب نسبت تعداد عناصر یکتایی که اضافه کردیم و اسلات های موجود و میتونه (O(1 میشه) حالا اگر یونیفورم نباشه زمان جست و جو میتونه تا (O(n هم بالا بره(البته حتی در صورت یونیفورم بودن هم اگر تعداد slot ها به نسبت عناصر کم باشه بازم  همین اتفاق میفته )
منظور از مرتب سازی هم این بود که مثلا با این روش هم میشه  تعداد k رو محاسبه کرد :
http://coliru.stacked-crooked.com/a/cea2cc1c0c1ba1af
 که nlogn هست و بسته به داده و hash function ای که وجود داره می تونه از hash table هم سریع تر باشه .

---

از شبه کد اینطور فهمیدم که اول عناصر مرتب میشند بعد متغیر counter با زمان n میاد عناصر قبلی رو count میکنه با k مقایسه میشه و مقدار اون عنصر رو برمی گردونه.
من نمی خوام عناصر رو مرتب کنم!
دارم آماری count میکنم

---

اصلا بحث سر این که میخواین sort کنید یا نه نیست !
منظور من این بود که روش هایی سریع تر از hash table  بسته به داده ای که دارید هم وجود داره (داخل  سوال مگه نگفتید "سریع ترین الگوریتم برای این مسئله چیست ؟")

Answer 3

روشی که پیشنهاد کردم رو در عکس آوردم

به نظرم برای اینکه بحث مون به جاهای  خوبی برسه میشه 2 کار انجام داد :

1- اثبات اینکه این مسئله امگای nlog n هست

یا

2- یک مثال نقض در روشی که گقتم

با تشکر

 

 

(اگر سایت  یک نرم افزاری مثله openlatexeditor   داشت خوب میشد )

Comments

در صورتی الگوریتم شما (O(n میشه که بتونید برای هر آرایه (شامل عضو عددی یا غیر عددی ) 2 کار زیر رو با (1)O انجام بدید
1_ به شکلی تگ بزارید که 2 عنصر "متفاوت" از آرایه اصلی به  2 خونه متفاوت از آرایه تعداداشاره کنن (ضمنا خود عملیات تگ گذاشتن هم باید (1)O باشه)
2_ وقتی که عنصر تکراری پیدا شد.( مثل داخل شکلی که گفتید وقتی که به -100 که داخل خونه سوم رسیدید ) باید  شمارنده k رو با (1)O  بیشتر کنید .
که عملا انجام این 2 کار همزمان برای آرایه با عضو های  نامشخص(مثلا غیر عددی) ممکن نیست .

---

ممنون
در مورد hash function به نظر می رسه همچین تابعی نداریم چون اگر از درهم سازی جامع هم بخایم استفاده کنیم باز هم نیاز به مقایسه است :)