یک راه استفاده از hash table هستش که در این صورت مرتبه اجرایی الگوریتم میشه [tex]O(m n)[/tex]. (با این فرض که تعداد عناصر آرایه‌های A و B رو m و n در نظر بگیریم.) اگر فرض کنیم n=m اونوقت از مرتبه بیگ اوی n خواهد بود.

پ.ن: این سوال باید راه حلی بدون استفاده از hash table هم داشته باشه چون گفته شده در بهترن حالت از مرتبه بیگ اوی n و در بدترین حالت از مرتبه بیگ اوی nlgn درصورتی که اگر از hash table استفاده بشه هر دو حالت از مرتبه بیگ اوی n میشن.

(۲۹ شهریور ۱۳۹۱ ۱۱:۰۴ ب.ظ)mfXpert نوشته شده توسط:  پ.ن: این سوال باید راه حلی بدون استفاده از hash table هم داشته باشه چون گفته شده در بهترن حالت از مرتبه بیگ اوی n و در بدترین حالت از مرتبه بیگ اوی nlgn درصورتی که اگر از hash table استفاده بشه هر دو حالت از مرتبه بیگ اوی n میشن.

نمیشه این کارو کرد؟
اول هرکدوم از لیست ها رو با nlgn مرتب کنیم ، بعد به ازای n تا عنصر یه لیست تو اون لیست دیگه با lgn بگردیم که اون عنصر وجود داره یا نه ، اینجوری میشه nlgn.
ها؟

کلا این اجتماع و اشتراک مربوط به درهم سازی میشه؟آخه تو تستای مرتب سازی بود؟فقط جواب گفته بدترین حالت:
n logn و بهترین حالت: n

(۳۰ شهریور ۱۳۹۱ ۱۰:۲۶ ق.ظ)mahtab_rafiei نوشته شده توسط:  کلا این اجتماع و اشتراک مربوط به درهم سازی میشه؟آخه تو تستای مرتب سازی بود.

نه لزوما

الان من تو پوران نگاه کردم نوشته :
گزینه ۴ صحیح است (nlgn و nlgn).
کلید طراح گزینه ۲ است(n و nlgn).ولی می توان با مرتب سازی و n بار جستجوی دودویی به جواب رسید.از آنجایی که از اعداد اطلاعی نداریم نمی توان مثلا از درهم سازی استفاده کرد.