تالار گفتمان مانشت

دو لیست نامرتب A, B هر کدام با N عنصر داده شده اند میخواهیم به صورت بهینه لیست [tex]A\cap B[/tex] را بدست اوریم.زمان اجرای بهینه این الگوریتم در دو حالت میانگین و بدترین حالت چقدر است؟

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

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

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

(30 شهریور 1391 10:26 ق.ظ)mahtab_rafiei نوشته شده توسط: [ -> ]کلا این اجتماع و اشتراک مربوط به درهم سازی میشه؟آخه تو تستای مرتب سازی بود.

نه لزوما

(29 شهریور 1391 11:04 ب.ظ)mfXpert نوشته شده توسط: [ -> ]پ.ن: این سوال باید راه حلی بدون استفاده از hash table هم داشته باشه چون گفته شده در بهترن حالت از مرتبه بیگ اوی n و در بدترین حالت از مرتبه بیگ اوی nlgn درصورتی که اگر از hash table استفاده بشه هر دو حالت از مرتبه بیگ اوی n میشن.

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

(30 شهریور 1391 03:05 ب.ظ)Marcel نوشته شده توسط: [ -> ]

(29 شهریور 1391 11:04 ب.ظ)mfXpert نوشته شده توسط: [ -> ]پ.ن: این سوال باید راه حلی بدون استفاده از hash table هم داشته باشه چون گفته شده در بهترن حالت از مرتبه بیگ اوی n و در بدترین حالت از مرتبه بیگ اوی nlgn درصورتی که اگر از hash table استفاده بشه هر دو حالت از مرتبه بیگ اوی n میشن.

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

لسیت رو با nlogn مرتب،بعد جستجوی دودویی واسه پیدا کردن یه عنصر میشه از مرتبه logn حالا واسه جستجوی n عنصر میشه nlogn
2nlogn که باز میشه از مرتبه nlogn

حالت میانگین: چطور بدست میاد؟حالت میانگین با این روش n نمیشه

(30 شهریور 1391 04:35 ب.ظ)mahtab_rafiei نوشته شده توسط: [ -> ]حالت میانگین: چطور بدست میاد؟حالت میانگین با این روش n نمیشه

نه ،واسه این روش هر سه حالت nlgn میشه.چون مرج سورت همیشه میشه nlgn .
این سوال ماله چه سال و چه رشته اییه؟

(30 شهریور 1391 06:03 ب.ظ)Marcel نوشته شده توسط: [ -> ]

(30 شهریور 1391 04:35 ب.ظ)mahtab_rafiei نوشته شده توسط: [ -> ]حالت میانگین: چطور بدست میاد؟حالت میانگین با این روش n نمیشه

نه ،واسه این روش هر سه حالت nlgn میشه.چون مرج سورت همیشه میشه nlgn .
این سوال ماله چه سال و چه رشته اییه؟

مهندسی کامپیوتر 90

ا

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