دوستان سلام.دوتا لیست مرتب داریم و می خوایم اشتراک این دو تا لیست رو در بهترین زمان بدست بیاریم و اون رو با کد پیاده سازی کنیم.لطفا مثل همیشه راهنمایی کنید.ممنون
(۱۷ اسفند ۱۳۹۲ ۰۲:۴۱ ب.ظ)mohsen kaedi نوشته شده توسط: دوستان سلام.دوتا لیست مرتب داریم و می خوایم اشتراک این دو تا لیست رو در بهترین زمان بدست بیاریم و اون رو با کد پیاده سازی کنیم.لطفا مثل همیشه راهنمایی کنید.ممنون
اعضای لیست کوچکترو (مثلا تعدادشون kتاست)توی لیست بزرگتر (مثلا تعدادش nتاست) با جستجوی دودویی جستجو می کنیم که می شه
klogn
اگر اعضای دو مجموعه با هم برابر باشند، این الگوریتمی که شما گفتید از مرتبهی $O(nlogn)$ میشه. البته فکر میکنم این حالت زمانی مناسب است که دست کم یکی از لیستها نامرتب باشند.
فکر میکنم میشه از الگوریتم ادغام استفاده کرد و آن هم مرتبهی زمانی برابر با $O(n)$ داره.
همینطور تا جایی که یادم هست میشه این کار رو با استفاده از ایدهی Hashing با ضریب بار مناسب، در مرتبهی $O(n)$ انجام داد.