اگه یه متغییر رو بخایم تو یه آرایه چک کنیم که وجود داره یا نه ، بهترین الگوریتم چیه؟
این فرض اش اینه که تعداد آرایه مون بسیار زیاده (مثلا 3000 تا یا بالاتر) حالا اینکه مثلا میخایم 20 تا متغییر رو چک کنیم که تو این 3000 تا آرایه وجود داره یا نه؟
فقط همین روش وجود داره که دونه دونه چک کنیم هر متغییر رو؟ یعنی 20*3000 یعنی 60000 بار باید اجرا شه کدمون تا مشخص بشه؟ یا اینکه راه بهتری هم هست؟
ravegoat
03-08-15, 20:25
الزاما تعداد تکرار ها به دو دلیل در این مقایسه 60000 نخواهد بود:
وقتی ما متغیر اول رو در آرایه جست و جو می کنیم، شاید درآیه 10 ام آرایه با مقدار متغیر اول برابر باشه و در نتیجه نیازی نیست درآیه های 11 ام، 12 ام و الی آخر بررسی بشن. این حرف برای سایر متغیر ها هم صادقه.
اگر متغیر ها مقادیر متفاوتی در مقایسه با هم داشته باشن وقتی ما متغیر مورد نظر رو درون آرایه پیدا کردیم، می تونیم اون درآیه رو حذف کنیم. طبق مثال بالا اگه درآیه 10 ام برابر با متغیر اول شد، می تونیم درآیه ی 10 ام رو از آرایه حذف کنیم. در نتیجه به هنگام بررسی متغیر بعدی به جای 3000 المان، با 2999 المان سر و کار خواهیم داشت. این روند کاهشی تا آخرین متغیر می تونه ادامه پیدا کنه.
در کل بنده غیر از مقایسه ی نظیر به نظیر در این مساله، الگوریتمی با پیچیدگی کم تر سراغ ندارم ولی شاید دوستانی که در این زمینه فعالیت دارن، بتونن راه حل های سریع تری پیشنهاد بدن. البته در سایر مسایل مربوط به مقایسه میشه از مزیت های Hash Function استفاده کرد (نه در این مساله) که نمونه ای از اون در مقاله ی زیر تشریح شده:
Only the registered members can see the link
به علاوه اگر آرایه قابل Sort کردن باشه، شاید بشه سرعت مقایسه رو افزایش داد ولی این حکم در حالت کلی درست نیست. اطلاعات بیش تر:
Comparison of Unique Array Element Checking Algorithms - CodeProject (Only the registered members can see the link)