الگوریتمی برای مقایسه‌ی دو لیست مرتب

[DumanNazeri]

سلام. وقت بخیر. خسته نباشید.
می‌خواستم ببینم بهینه‌ترین و بهترین الگوریتم برای مقایسه‌ی دو لیست مرتب کدومه؟!
یعنی بگه کدوم یک از عنصرهای لیست اول تو لیست دوم هم هستن؟!
من اینُ پیدا کردم اما استادم گفت از این بهینه‌تر هم هست...


col = 1;
for i = 1 to n do
for j=col to n do
if ( a[i] == b[j] )
{
col = j;
cout << i << j;
}


col متغیری هست که مقدار Collision ( محل برخورد! وقتی عنصر مشابه پیدا می‌شود. ) را در خود ذخیره می‌کند..
ممنون می‌شم اگر راهنمایی بفرمایید..
روز خوش.

[Davidd]

سلام. اين الگوريتمي كه نوشتي مرتبه زماني n به توان 2 داره. در صورتي كه وقتي ليست مرتبه ديگه نبايد از جستجوي خطي استفاده كني ميشه از جستجوي دودويي استفاده كرد. بنابراين اگه حلقه دومي به جستجوي دودويي تبديل بشه مرتبه زماني n lg(n) ميشه. اما مرتبه زماني از اين هم ميتونه كمتر بشه چون هر دو ليست مرتب هستن. كمترين مرتبه زماني براي اينكار مرتبه خطي 2n هست. روش كار هم مثه ادغام دو ليست مرتب هست اگه الگوريتم ادغام (merge) دو ليست مرتب ببيني متوجه ميشي. بايد روي هر ليست يه شمارنده تعريف كني مثلا i و j . دو سر ليست مقايسه كني (يعني A[i] و B[j] ) و اگه دو عدد سر ليست مساوي بود يعني مشترك هست در غير اينصورت شمارنده روي ليستي كه عددش كوچيكتره حركت ميكنه و به همين ترتيب تا به انتهاي يكي از ليست ها برسي.

[alisafaie]

وقتی پای جستجو و بهینه سازی وسط میاد باید سراغ الگوریتم های جستجو برید و بسته به حجم اطلاعات و نوع داده و مرتب بودن یا نبودن اون از الگوریتم های مختلف استفاده کنید.چند نمونه از این الگوریتم ها جستجوی حبابی یا درختی و ... است. هرکدام مزایا و معیب خودشون رو دارند. من فکر می کنم منظور استاد شما استفاده از الگوریتم های جستجو بوده تا شما را با این مباحث آشنا کند.

جستجو کنید. برای الگوریتم های مختلف در اینترنت پیاده سازی های زیادی نوشته شده است.

به عنوان نمونه

#Searching and Sorting Algorithms via C (http://www.codeproject.com/Articles/177363/Searching-and-Sorting-Algorithms-via-C)