سلام.
اگر فرض کنیم آرایه اول دارای n و دومی m عضو فک می کنم بشه تتای(n*m) اگه درسته بگو استدلالمو بگم اگرم نیست که هیچی دیگه :دی

نه غلطه.
میانگین: O-n
بدترین: O-nlogn

مقسمی فقط گزینه داده.

منظورش از اشتراک اینه؟
۲ ۴ ۳ ۱ ۲ ۱
۱ ۲ ۳ ۲ ۴ ۱ ۲
که اشتراکش می شه:
۲ ۳ ۱
ینی من در واقع بزگ ترین اشتراکشون رو گفتم.
یا اینکه چنتا عضوشون مشترکه؟
لطفا اعداد رو از سمت راست بخون (شکلک طراح سوال کنکور :دی)

سلام
فرض کنید یه دسته m عضو و یه دسته n عضو داره
با اونی که کوچکتر مثلا فرض کن n<m بیا یه درخت btree بساز nlogn
یعد یکی یکی عناصز اون یکی لیست یعنی لیست m رو بیا جستجو کن در درخت ساخته شده با n عضو
هزینه جستجو در درخت باینری log n بود دیگه . ما هم که m تا عضو داریم پس هزینه چک کردن کل m عضومون میشه mlogn
پس رسیدیم به nlogn + mlog n
پس o(nlogn
متوسط رو هم نمی دونم اما فکر کنم اکه دو تالیست مرتب باشن با ادغام می شه O(N می تونیم اشتراکشون رو در بیاریم

شاید بشه از هش تیبل استفاده کرد(جدول هش زنجیره ای) که زمان جست و جو در بدترین حالت On و در حالت متوسط از O n/m
هستش که n/m همون فاکتور لودش هستش ...
که درکل می شه On

---

برای حالت متوسط یه راه دیگه هم می شه گفت.
اول دوتارو مرتبط کنیم بعد با جست و جوی باینری دنبال اعدادمون بگردیم که می شه

۲nlogn + 2 logn = Onlong
با فرض n بودن تعداد عناصر هر دو آرایه.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.