به نظرم جواب مقسمی درسته

بدترین حالتش که مشخصه اما میانگینشو نمی دونم چرا شد اوی n!!
هر روز یه الگوریتم میاد اینارو بهبود میده اما خوب بعضیاشم ثابت شده که بهتر از این نمیشه. حالا ما چطور اینا رو یاد بگیریم. من کلا از این جور سوالا خیلی بدم میاد. مرتبه زمانیا رو می گم. یه سرچ بزنین تو ویکی خودشونم موندن تو خیلی از این موارد.
ای کاش یکی پیدا شه تمام این الگوریتمای معروفو به ترتیب زمانهای میانگین و بدترین و بهترینشو اینجا بگذاره تا همه استفاده کنن و مشکلات حل شه.

(۳۰ دى ۱۳۹۱ ۰۷:۴۷ ب.ظ)۸Operation نوشته شده توسط:  مقسمی گزینه ۲ رو زده و کتاب کنکور سنجشم گفته سوال حذفیه!

بنظر میاد فقط از تکنیک هشینگ بشه به مرتبه اوی n رسید؛ یعنی لیست اول رو یکی یکی نگاشت کنیم در یک فضای آدرس کمکی؛
و بعد همین کارو با عناصر لیست دوم انجام بدیم؛ هر جا کالیژن اتفاق افتاد عناصر دارای کالیژن با هم مقایسه میشن؛ از اونجایی که در حالت میانگین دسترسی به هر عنصر با تکنیک هشینگ از اوی ۱ هست، متوسط کل زمان اجرا اوی n میشه؛
منتها این روش (اگه درست باشه) فکر میکنم بدترین زمان اجراش n2 هست (طول زنجیر تداخلی که تشکیل میشه از مرتبه n باشه)؛

(۰۱ بهمن ۱۳۹۱ ۱۲:۱۱ ق.ظ)mfXpert نوشته شده توسط:  به نظرم جواب مقسمی درسته

دوستان عزیزی که به جواب رسیدن ممنون میشم توضیح بدن چجوری به این نتیجه رسیدن

(۰۱ بهمن ۱۳۹۱ ۱۲:۵۷ ق.ظ)Ghiasoddin نوشته شده توسط:  منتها این روش (اگه درست باشه) فکر میکنم بدترین زمان اجراش n2 هست (طول زنجیر تداخلی که تشکیل میشه از مرتبه n باشه)؛

فک می کنم پاسخ صحیح در سوال نبوده که حذف شده!

جواب سنجش اینه و کاملا درسته :
میانگین : teta_n
بدترین : teta_nLgn
-----------------
توضیح :
با روش درهم سازی می توان عناصر تکراری را یافت.بهترین تابع درهم ساز در حالت میانگین میشه : teta_n
--
ابتدا یکی از دو آرایه رو مرتب می کنیم و با جستجوی دودویی ،عناصر آرایه ی دوم رو توی آرایه ی مرتب اولی پیدا می کنیم.
جستجو میشه lgn که اگه برای n عنصر تکرا کنیم میشه توی بدترین حالت :
teta_nlgn
------------------------------
این جوابی که دادم کامل هست و اصلا شک نکن.
طبق سنجش هم گزینه ی ۲ درسته