جستجوی بهینه با شرایطی خاص

[saed2006]

یک ارایه دارم دارای n عنصر
هر عنصر دارای x و y خاص خود است
میخوام برای تمام عناصر مقدار متغیر بولین IsX IsYرو بدست بیارم
IsX هر ایتم وقتی صحیح میباشد که x ان ایتم با یکی از x های دیگر ایتم ها مساوی باشد
به همین نحو Isy
اگر بخوام جستجوی ترتیبی انجام بدم با فرض اینکه در ارایه n تا عنصر که هر عنصر m ایتم داشته باشد
الگوریتم مقدار m*n*m زمان بر خواهد بود که این یعنی فاجعه الگوریتم بهینه برای انجام این کار کدام است؟

[qwerty11]

به نظرم خیلی خوب توضیح ندادید و من برداشتی که از حرفاتون کردم رو میگم شایدم درست نباشه !

2 تا راه به ذهن من میرسه :

راه اول : اگر x و y عناصر خیلی بزرگ نیست 2 تا آرایه ی یه بعدی به طول max x و max y در نظر بگیر (مثلاً آرایه ی a و آرایه ی b). وقتی یه آیتم (بنا به تعریف شما) رو میخونی که دارای مشخصات X و Y هستش، به a[X] و b[Y] یکی اضافه کن. بعد از اینکه آیتم ها رو کامل خوندی حالا بیا دوباره از اول آیتم ها رو نگاه کن، برای هر آیتم اگر a[X] بزرگتر از یک بود یعنی isX اون آیتم true هستش و در غیر این صورت false. برای isY هم به همین ترتیب عمل کن. در این حالت پیچیدگیت n*(max x +max y) I هستش.

راه دوم : بیا عناصر هر آرایه رو یه بار بر اساس مقدار x ای که دارن و یه بار هم بر اساس مقدار y ای که دارن مرتب کن. حالا isX یه آیتم وقتی true هستش که یا عنصر قبلش دارای X برابر با خودش باشه یا عنصر بعدش. برای isY هم به همین ترتیب ... در این حالت پیچیدگیت n*m*log m هستش ...

[saed2006]

جزئیات بیشتر
http://www.barnamenevis.org/sh...d.php?t=230554