معلوم کنیم در یک آرایه، اعداد تکراری هست یا نه

[Kensington]

سوال: راهی پیشنهاد کنید با پیچیدگی O -nLogn که مشخص کند آیا عدد تکراری در یک آرایه n عضوی وجود دارد یا نه . ( لازم نیست اعداد تکراری رو مشخص کند. همین که به یک مورد تکراری برسد هم کافیه)

نظر من: بالاخره اول باید سورتش کنیم ( درسته ؟ ) . هیچ روش سورتی هم نداریم از نوع مقایسه ای که بهتر از nLgn باشه. پس چکار کنیم که حالا این کار اضافی هم میخواهیم روی آرایه انجام دهیم، از nLgn بالا نزنه؟:اشتباه:

[BOB]

سلام

در كل همان nLogn ميشود. ميتوانيد در حين مرتب سازي و مقايسه عناصر، برابري آنها را هم بررسي كنيد.
و يا در غير اينصورت، اگر اول كل آرايه را مرتب كنيد، پس از آن با يك جستجوي n/2 ميتوان عنصر تكراري را پيدا كرد.
كه البته nLogn + n/2 همان nLogn است.

[Kensington]

n/2 رو average case گرفتید که اعداد تکراری در میانه آرایه باشند؟ یا از جای دیگری آمده؟
اگه بدترین حالت رو وقتی بگیریم که دوتا اعداد تکراری در دو خانه آخر آرایه باشند n-1 مقایسه لازم داریم
بعد پیچیدگی کلی میشه n + nLgn .
پس nLgn + n از نظر Big O با nLgn برابر هستش؟

[BOB]

n/2 رو average case گرفتید که اعداد تکراری در میانه آرایه باشند
بله

البته n، n-1 و n/2 همگي از مرتبه خطي BigO(n) هستند. پس فرقي نميكند كه با nLogn جمع شوند يا خير، چرا كه nLogn مرتبه‌اي بزرگتر از خطي است و هميشه بزرگترين مرتبه، به عنوان BigO در نظر گرفته مي‌شود.

مثلا در n^2 + 3n^3 + 2nLogn بزرگترين مرتبه همان BigO(n^3) خواهد بود و مابقي قابل چشم پوشي هستند.

موفق باشيد
_________________________________________
آفرين بر شما كه به Tag گذاري اهميت ميدهيد.

[Mbt925]

nLogn یا nLog + ... که دوستان گفتم منطقی نیست.

چون قرار نیست برای هر بار که می خواین وجود عدد در آرایه رو بررسی کنید، اون رو مرتب کنید.

کافیه هنگام ساخت آرایه یا برای بار اول (در صورتی که آرایه توسط شما ساخته نمیشه) اون رو مرتب کنید و مرتب نگه دارید.

در اینصورت می تونید با یه Binary Search با مرتبه Logn/2 وجود/عدم وجود عدد در آرایه رو بررسی کنید.

[xxxxx_xxxxx]

من پيشنهاد مي كنم از الگوريتم پارتيشن استفاده كنيد.
با كمي تغيير ميشه به نتيجه رسيد.
من يه نمونه مشابه قبلا تو همين بخش گذاشتم.
البته اون براي كار ديگه اي بود ولي با تغييرات جزئي ميشه درستش كرد

[Kensington]

nLogn یا nLog + ... که دوستان گفتم منطقی نیست.

چون قرار نیست برای هر بار که می خواین وجود عدد در آرایه رو بررسی کنید، اون رو مرتب کنید.

کافیه هنگام ساخت آرایه یا برای بار اول (در صورتی که آرایه توسط شما ساخته نمیشه) اون رو مرتب کنید و مرتب نگه دارید.

در اینصورت می تونید با یه Binary Search با مرتبه Logn/2 وجود/عدم وجود عدد در آرایه رو بررسی کنید.

-سوال رو دقت نکردید. نمیخواهیم وجود عدد تکراری خاصی در آرایه رو بررسی کنیم.
تا همین مشخص کند که آیا عددی تکراری در آرایه هست یا نیست، کافیه.
- آرایه هم به ما داده شده. ما نمیسازیمش.
- چون دنبال عدد خاصی نیستیم، باینری سرچ به کارمان نمی آید. چون باید برای n تا عدد فراخوانیش کنیم که میشود همان nLogn .

[Kensington]

من پيشنهاد مي كنم از الگوريتم پارتيشن استفاده كنيد.
با كمي تغيير ميشه به نتيجه رسيد.
من يه نمونه مشابه قبلا تو همين بخش گذاشتم.
البته اون براي كار ديگه اي بود ولي با تغييرات جزئي ميشه درستش كرد

پارتیشن یعنی pivot ؟ یعنی همان روش quick sort ?
اگر منظورتون اونه، بهتره استفاده نکنیم چون کوییک سورت گاهی هم به O of N^2 میرسه.
در حالیکه با nLgn کارمان راه میفته.

* راستی نمیشه توی این ادیتور نمادهای ریاضی مثل همین توان و ... رو نوشت؟

[Kensington]

پس کدش چیزی شبیه این شد:



Boolean AreDistinct ( Array A [1..n])
HeapSort(A )
for i: 2 to n do
if A[i] = A[i-1] then return False
Return True