دو لیست نامرتب 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
(۳۰ شهریور ۱۳۹۱ ۱۰:۲۶ ق.ظ)mahtab_rafiei نوشته شده توسط: کلا این اجتماع و اشتراک مربوط به درهم سازی میشه؟آخه تو تستای مرتب سازی بود.نه لزوما
(۲۹ شهریور ۱۳۹۱ ۱۱:۰۴ ب.ظ)mfXpert نوشته شده توسط: پ.ن: این سوال باید راه حلی بدون استفاده از hash table هم داشته باشه چون گفته شده در بهترن حالت از مرتبه بیگ اوی n و در بدترین حالت از مرتبه بیگ اوی nlgn درصورتی که اگر از hash table استفاده بشه هر دو حالت از مرتبه بیگ اوی n میشن.
نمیشه این کارو کرد؟
اول هرکدوم از لیست ها رو با nlgn مرتب کنیم ، بعد به ازای n تا عنصر یه لیست تو اون لیست دیگه با lgn بگردیم که اون عنصر وجود داره یا نه ، اینجوری میشه nlgn.
ها؟
(۳۰ شهریور ۱۳۹۱ ۰۳:۰۵ ب.ظ)Marcel نوشته شده توسط:(29 شهریور ۱۳۹۱ ۱۱:۰۴ ب.ظ)mfXpert نوشته شده توسط: پ.ن: این سوال باید راه حلی بدون استفاده از hash table هم داشته باشه چون گفته شده در بهترن حالت از مرتبه بیگ اوی n و در بدترین حالت از مرتبه بیگ اوی nlgn درصورتی که اگر از hash table استفاده بشه هر دو حالت از مرتبه بیگ اوی n میشن.
نمیشه این کارو کرد؟
اول هرکدوم از لیست ها رو با nlgn مرتب کنیم ، بعد به ازای n تا عنصر یه لیست تو اون لیست دیگه با lgn بگردیم که اون عنصر وجود داره یا نه ، اینجوری میشه nlgn.
ها؟
لسیت رو با nlogn مرتب،بعد جستجوی دودویی واسه پیدا کردن یه عنصر میشه از مرتبه logn حالا واسه جستجوی n عنصر میشه nlogn
۲nlogn که باز میشه از مرتبه nlogn
حالت میانگین: چطور بدست میاد؟حالت میانگین با این روش n نمیشه
(۳۰ شهریور ۱۳۹۱ ۰۴:۳۵ ب.ظ)mahtab_rafiei نوشته شده توسط: حالت میانگین: چطور بدست میاد؟حالت میانگین با این روش n نمیشه
نه ،واسه این روش هر سه حالت nlgn میشه.چون مرج سورت همیشه میشه nlgn .
این سوال ماله چه سال و چه رشته اییه؟
(۳۰ شهریور ۱۳۹۱ ۰۶:۰۳ ب.ظ)Marcel نوشته شده توسط:(30 شهریور ۱۳۹۱ ۰۴:۳۵ ب.ظ)mahtab_rafiei نوشته شده توسط: حالت میانگین: چطور بدست میاد؟حالت میانگین با این روش n نمیشه
نه ،واسه این روش هر سه حالت nlgn میشه.چون مرج سورت همیشه میشه nlgn .
این سوال ماله چه سال و چه رشته اییه؟
مهندسی کامپیوتر ۹۰
ا
الان من تو پوران نگاه کردم نوشته :
گزینه ۴ صحیح است (nlgn و nlgn).
کلید طراح گزینه ۲ است(n و nlgn).ولی می توان با مرتب سازی و n بار جستجوی دودویی به جواب رسید.از آنجایی که از اعداد اطلاعی نداریم نمی توان مثلا از درهم سازی استفاده کرد.