سلام دوستان
سوالات ساختمان و الگوریتم حرصمو در میاره
سوالم در مورد یک موضوعه واحده چند بخشش کردم و تاپیک جدید نزدم
۱- فرض کنید دو ارایه داریم مرتب ( تکراری داخل ارایه نداریم) میخواهیم اشتراک دو ارایه رو مشخص کنیم ( تمام عناصر مشترک) روش پیشنهادی شما چیه و مرتبه اجرایش؟
۲- باز هم دو ارایه مرتب و عنصر تکراری تو هر ارایه نداریم اینبار میخواهیم kامین عنصر مشترک رو پیدا کنیم( مثلا ارایه ۵۰,a= 1,2,3,4,8,9 و ارایه b=1,50,4,9,100,200 که عدد یک اولین عنصر مشترک و عدد ۴ دومین عنصر مشترک و عدد ۹ سومین عنصر و عدد ۵۰ بر اساس ارایه b دومین عنصر هست و بر اساس a هفتمین عنصر) روش پیشنهادی؟
سؤال ۱:
طبیعیه چون آرایه‌ها مرتب هستند و عنصر تکراری نداریم، با یک پیمایش ساده از اولین عنصر یکی از آرایه‌ها می‌تونید اشتراک رو بدست بیارید.
فرض کنید دو آرایه‌ی ما به ترتیب ۱-۲-۳-۴-۵-۱۰ و دومی ۸-۹-۱۰-۱۱ باشه. از آرایه‌ی اول شروع میکنید و با عنصر اول آرایه‌ی دوم مقایسه میکنید. اگر درایه‌ی اول آرایه‌ی دوم از عنصر اول آرایه‌ی اول، کوچکتر بود، با عنصر دومی آرایه‌ی دوم مقایسه میکنید و چون مرتب هستند، دیگه نیازی به برگشت به درایه‌ی اول آرایه‌ها در هر مقایسه نیست.
بنابراین با فرض اینکه بزرگترین آرایه دارای n عنصر باشه، مرتبه‌ی این کار از [tex]O(n)[/tex] میشه.
برای سؤال دوم:
یک اشکالی در سؤال دارید که فکر می‌کنم در مثال، آرایه‌ی دوم رو مرتب ننوشتید.
به نظرم میشه طبق روالی که در بالا توضیح دادم عمل کنید و با یک جستجوی خطی در آرایه‌ای که عناصر مشترک رو نوشتید، kامین عنصر را پیدا کنید. یعنی با مرتبه‌ی [tex]O(n k)[/tex] یا به عبارتی همان [tex]O(n)[/tex]
البته اگر بخواهیم کامل‌تر در اینباره صحبت کنیم، باید بگیم که در بهترین حالت، این کار میتونه از مرتبه‌ی [tex]O(k)[/tex] انجام بشه. چرا؟ چون فرض کنید دقیقاً دو آرایه k عنصر ابتداییشون با هم یکی هست. در نتیجه طبق روش بالا، ما فقط k عنصر رو بررسی می‌کنیم و وقتیکه بهش رسیدیم روند جستجو رو متوقف کنیم و خروجی رو اعلام کنیم.
ضمن اینکه این فرض بهترین حالت هم میتونه تبدیل به روند حالت اول یعنی همون تحلیل [tex]O(n)[/tex] بشه چون ما هیچ اطلاعی از k و مقدارش نداریم. بنابراین میشه اینطور نتیجه گرفت که اگر k کوچکتر از n باشه، در بهترین حالت ما با مرتبه‌ی [tex]O(k)[/tex] میتونیم به این موضوع دست پیدا کنیم.
(۰۵ دى ۱۳۹۳ ۰۳:۱۵ ق.ظ)Mohammad-A نوشته شده توسط: سؤال ۱:بابت پاسخ متشکرم
چون آرایه‌ها مرتب هستند و عنصر تکراری نداریم، با یک پیمایش ساده از اولین عنصر یکی از آرایه‌ها می‌تونید اشتراک رو بدست بیارید.
و اگر ارایه ما نامرتب باشه؟ باید اول مرتبشون کنیم تا بشه k امین عنصر مشترک رو پیدا کرد؟؟؟؟؟؟؟؟ یا راه دیگه هم داره که مرتبه اش خطی بشه؟
شاید بشه با یک تابع درهم‌سازی عناصر دو آرایه رو پویش کرد و در نهایت دید که آیا اشتراک دارند یا نه. این از مرتبه‌ی خطی است البته بعید میدونم با این روش بشه kامین عنصر مشترک رو بدست آورد. با فرض اینکه m عنصر مشترک بین دو آرایه وجود داشته باشه، میشه گفت مرتبه‌ی پیدا کردن kامین عنصر مشترک به صورت [tex]O(n mlogm k)[/tex] خواهد بود که نمیشه با قاطعیت گفت از [tex]O(n)[/tex] هست یا نه.
البته یک راه دیگه هم میتونه به این شکل باشه که بعد از اینکه عناصر مشترک آرایه پیدا شد، kامین کوچکترین عنصر رو با الگوریتم پارتیشن، محور قرار بدیم که از مرتبه‌ی [tex]O(m n)[/tex] خواهد بود.
اما همه‌ی اینها بستگی به این داره که تابع درهم‌ساز ما چقدر کاراست.
اما راه کلی و عمومی‌تر همینه که دست کم یکی از از آرایه‌ها رو در nlogn مرتب کنیم و از آرایه‌ی دیگه شروع کنیم و با جستجوی دودویی عناصر مشترک رو پیدا کنیم که میشه ۲nlogn
(۰۵ دى ۱۳۹۳ ۰۹:۱۲ ب.ظ)Mohammad-A نوشته شده توسط: شاید بشه با یک تابع درهم‌سازی عناصر دو آرایه رو پویش کرد و در نهایت دید که آیا اشتراک دارند یا نه. این از مرتبه‌ی خطی استمتشکرم خیلی توضیحاتتون خوب بود
تو جاهای مختلف دیدم که میگن تابع درهم ساز و...
متوجه نمیشم از درهم ساز چطوری میشه برای الگوریتم مرتب سازی یا مسایل اینطوری استفاده میشه
نقل قول: میشه گفت مرتبه‌ی پیدا کردن kامین عنصر مشترک به صورت $O(n+mlogm+k)$ خواهد بود که نمیشه با قاطعیت گفت از $O(n)$ هست یا نه.ممنون میشم بفرمایید که چطوری مرتبه اش این شد
ببینید از درهم‌سازی برای مرتب‌سازی استفاده نمیشه. آرایه‌ای که ما داریم رو با استفاده از یک تابع درهم‌ساز پویش می‌کنیم تا یه سری اطلاعات از این آرایه بتونیم بدست بیاریم.
مثلاً فرض کنید تابع درهم‌ساز ما [tex]f(x)=x\: \mod\: 7[/tex] باشه. اینطوری میشه همه‌ی آرایه رو به سادگی به باقی‌مانده‌های تقسیم بر عدد هفت افراز کرد.
حالا اینکه اینجا چه کاربردی داره. گفتم به هر حال شاید روش مطمئنی نباشه. یعنی دست کم باید اطلاعاتی از آرایه‌ها داشت (شاید!) و وقتیکه ما دو آرایه رو با استفاده از یک تابع درهم‌ساز پیمایش کردیم، میتونیم جاهایی که عنصر مشترک داشتند، پیدا کنیم.
برای مرتبه‌ای که پرسیدید:
با فرض اینکه ما از یک تابع درهم‌ساز استفاده کردیم و موارد مشترک بین دو آرایه رو پیدا کردیم، و با این فرض که m عنصر مشترک دو آرایه داشته باشند، میتونیم در mlogm این عناصر مشترک رو پیدا کنیم و با یک پیمایش در [tex]O(k)[/tex] عنصر مورد نظر رو پیدا کنیم.
البته گفتم این روش قطعی نیست و میشه روش بهتری طبق همان چیزی که گفتم یعنی استفاده از الگوریتم پارتیشن ارائه داد.
بسیار عالی
ممنونم
متوجه شدم
چون خوب توضیح میدید من جسارتا بازم سوال دارم
ادغام این ارایه ها ( در حالت نامرتب و مرتب ) چه روشهایی رو پیشنهاد میدید[/quote]