سئوال 57 کنکور ارشد 88

[Developer Programmer]

سه تا سئوال تقریبا مشابه به هم هستن که در کتاب جعفرنژاد و هم در کنکور 88 اومدن؛
متن هر دو سئوال رو میزارم ... دوستان لطف کنن به طور تشریحی توضیح بدن که پیچیدگی رو چطور به دست میارن


سئوال 57) A یک آرایه n عضوی با اعضاء غیر تکراری و B یک آرایه m عضوی با اعضاء غیرتکراری هستند و m<n میخواهیم آرایه C طوری بیابیم که اعضا AوB در آن وارد شده باشد و عضو تکراری هم نداشته باشیم. بهترین الگوریتم برای اینکار چه زمانی نیاز دارد؟


کتاب جعفرنژاد صفحه 333) فرض کنید S , T دو آرایه به ترتیب با n , m عنصر باشد نشان دهید الگوریتمی که همه عناصر مشترک را یافته و در آرایه U نگهداری کند را میتوان در زمان تتای (n+m) انجام داد

کتاب جعفر نژاد صفحه 336) فرض کنید S,T دو آرایه هر یک با n کلید غیر نزولی باشند؛ ثابت کنید الگوریتمی که بتواند میانگین همه 2n عنصر را بیابد تتای( log n) است

[manager]

من رو دو تا سوالای بعدی فکر نکردم گفتم اول سوال 57 طراحی الگوریتم رو جواب بدم بعدا. ما در حالت کلی باید n یا m عنصر رو ابتدا در C بریزیم بعدا بیائیم اون یکی آرایه رو به C اضافه کنیم. در نظر بگیرید شما اول A یا B رو بریزید تو آرایه C بعد به ازای هر عنصر آرایه دوم که می خواهید تو C درج کنید ببینید که آیا این عنصر در آرایه وجود دارد یا خیر که زمان مصرفی در این حالت برابر (O(nm هست.
راه حل بهینه تر اینه که شما آرایه کوچکتر رو مرتب کنید و سپس به ازای هر عنصر آرایه بزرگتر با استفاده از جستجوی دودوئی چک کنیدکه آیا این عنصر در آرایه دیگر وجود دارد یا خیر. شما یک mlogm برای مرتب سازی خرج می کنید و یک nlogm برای درج آرایه دیگر که زمان کلی برابر می شود با nlogm+mlogm=(n+m)logm.

[Developer Programmer]

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

[manager]

شما به ازای هر عنصر از آرایه A یک جستجوی دودئی با زمان مصرفی (O(logm بر روی آرایه B انجام می دهید که در کل nlogm هزینه زمانی برای درج آریه دوم و بزرگتر دارید.

[pesar irooni]

سوال 57 که تابلو بود باید از BST استفاده کنیم. ساخت یک BST برای n عنصر زمان nlogn و درج هر عنصر logn طول میکشه. کلا درخت جستجوی دودویی توی تعریف اصلی اش اومده که عنصر تکراری نداره. ما اول با آرایه کوچکتر شروع میکنیم و اونو در زمان mlogm میسازیم و بعد عناصر آرایه بزگتر رو تو همون درخت درج میکنیم که n تا عنصر با زمان درج هر عنصر logm که جمعا میشه mlogm + nlogm = (n+m)logm
در مورد سوا آخر هم شما با استفاده از یک الگوریتم تقسیم و حل میانه 2 آرایه رو میشه پیدا کرد. اول میانه آرایه اول و بعد میانه آرایه دوم رو پیدا میکنی و سپس بین این دو میانه (یعنی اعداد کوچکتر از میانه بزگتر و بزرگتر از میانه کوچکتر) دو آرایه مرتب رو تشکیل میدهند که همین روش رو تا رسیدن به میانه دو آرایه دنبال میکنیم.

[Developer Programmer]

ساخت یک BST برای n عنصر زمان nlogn و درج هر عنصر logn طول میکشه
اگه اشتباه نکرده باشم درخت BST درخت کامل نیست که ارتفاعش لگاریتمی باشه، پس عمل حذف و درج از مرتبه O(h) هستش

جواب سئوال دو رو از کتاب طراحی الگوریتم مقسمی پیدا کردم(صفحه 54)
اگر آرایه ها مرتب باشندبه کمک دو اشاره گر iوj که به ابتدی آرایه اشاره میکنن و یکی یکی جلو میروند میتوان اجتماع یا اشتراک دو آرایه رو در مدت زمان تتای (n+m) پیدا کرد

[manager]

به نظرم بهتره پای BST رو به این ماجرا باز نکنیم. بگیم جستجوی دودوئی در آرایه مرتب شده بهتره. اینجوری می تونیم logn رو قطعا تضمین کنیم.

[pesar irooni]

کاملا حق با شماست

[pesar irooni]

منظورم bst متوازن شده بود. مثلا AVL رو دقیقا با همان استدلال بالا

[mortezamsp]

سلام.
در مورد سوال اولی من فکرکنم بهترین زمان برای مرتب سازی یک آرایه بطول n برابر nlog n هست و در صورت مرتب بودن دو آرایه برای پیداکردن اشتراک یا اجتماع به زمان n نیاز هست.( اینو تو یکی از کتاب های ساختمان داده دیده بودم )
یعنی در کل میشه:
n log n + m log m + n ~ o( m+n * log m)1

درسته؟ نه ؟