فکر می کنم تو بدترین حالت بشه با مرتبه nlgn به جواب رسید.به این صورت که:یکی از دو تا لیست رو مرتب کنید(با مرتبه nlgn).حالا هرکدوم از عناصر اون یکی لیست که نامرتب هستش رو بردارید و با باینری سرچ تو لیست مرتب پیداش کنید.در کل مرتبه این روشی که گفتم میشه:$\Theta (nlgn) \Theta (nlgn)=\Theta (nlgn)$

(۰۹ دى ۱۳۹۰ ۱۱:۲۵ ق.ظ)mfXpert نوشته شده توسط:  فکر می کنم تو بدترین حالت بشه با مرتبه nlgn به جواب رسید.به این صورت که:یکی از دو تا لیست رو مرتب کنید(با مرتبه nlgn).حالا هرکدوم از عناصر اون یکی لیست که نامرتب هستش رو بردارید و با باینری سرچ تو لیست مرتب پیداش کنید.در کل مرتبه این روشی که گفتم میشه:$\Theta (nlgn) \Theta (nlgn)=\Theta (nlgn)$

تو بدترین حالت خودم هم همین رو بدست آوردم اما مشکل من تو حالت میانگینه که نمیدونم میشه همون nlognیا n حالت میانگین رو چه جوری در نظر بگیریم؟؟؟؟

نمیشه بگیم که دو لیست رو ادغام کنیم (به صورت نامرتب:یعنی یکی رو در انتهای دیگری قرار بدیم) بعد شروع کنیم BST بسازیم با این لیست ۲n عنصری (که در بدترین حالت میشه با ارتفاع n و در بهترین حالت میشه با ارتفاع nlgn) و در حین ساختن BST عناصر تکراری رو پیدا میکنیم....
جوابش کدوم گزینه هست هما جان؟سوال چه سالی هست؟

(۰۹ دى ۱۳۹۰ ۰۱:۱۱ ب.ظ)NoOne نوشته شده توسط:  نمیشه بگیم که دو لیست رو ادغام کنیم (به صورت نامرتب:یعنی یکی رو در انتهای دیگری قرار بدیم) بعد شروع کنیم BST بسازیم با این لیست ۲n عنصری (که در بدترین حالت میشه با ارتفاع n و در بهترین حالت میشه با ارتفاع nlgn) و در حین ساختن BST عناصر تکراری رو پیدا میکنیم....
جوابش کدوم گزینه هست هما جان؟سوال چه سالی هست؟

تست اول ساختمان داده ۹۰ بوده
اینی که شما میگید حداقل nlog n هست (البته جواب رو به ما میده )

فکر کنم ۲ بشه . اونایی که کتاب سنجش رو دارن لطفا جواب کتاب رو بزارن تا بررسی کنیم.

خوب با استدلال من میشه گفت گزینه ۴میشه.کسی نظری نداره؟

(۰۹ دى ۱۳۹۰ ۰۶:۴۲ ب.ظ)NoOne نوشته شده توسط:  خوب با استدلال من میشه گفت گزینه ۴میشه.کسی نظری نداره؟

اگه ۲ نباشه ۳ هست . آخه هر چی باشه با AVL در بدترین حالت در زمان nlog قابل پیاده سازیه

این سوال حذف شده

گزینه صحیح سه هست .
محال است در این سئوال بتوان به مرتبه ایی بهتر از nlgn دست یافت چه میانگین و چه بدترین حالت .
اصلا به راحتی میتوان اثبات کرد که الگوریتمی که بر مبنای مقایسه پایه ریزی شده باشه نمیتواند در زمان کمتر از nlgn اشتراک این دولیست را به دست اورد .
شاید طراح محترم فراموش کار بودن و یا این نکته رو فراموش کردن و یا اینکه خواستن به دواطلبان کنکور ۹۰ حال درست و حسابی بدن .

جای بسی تاسف هست شاهد چنین مواردی هستیم که در یک سال دو تا سئوال از پنج تا سئوال ساختمان حذف بشه . این هم به نحوی حق ناس هست که حق هزاران نفر رو پایمال میکنه .

در حالت خاص میتوان به مرتبه n دست یافت اما این فقط در حالت خاص امکان پذیر هست و با روشهایی شبیه الگوریتمهای مرتب سازی خطی و غیره (مثلا با باکت بندی مناسب یا حتی در هم سازی) اما مسئله اینه که این تنها در حالتهای خاص امکان پذیر هست و زمانی که هر دولیست ما از یکی الگو خاص پیروی کنن . که در اینجا هیچ اطلاعی از عناصر لیست نداریم و تنها راه همان مرتب سازی در زمان Nlgn ودر نهایت بقیه ماجرا

در کتاب نیپولیتان فصل ۷ تمرین ۱ صفحه ۳۳۶ سوالی مشابه داده شده با این مضمون
فرض کنید که s,t دو ارایه m,n عنصری باشند الگوریتمی بنویسید که تمامی عناصر مشترک را پیدا کند و انها را در ارایه u ذخیره کند نشان دهید که این کار می تواند در زمان (n+m)تتا انجام شود
اگر چنین است پس جواب سوال کنکور( n)تتا است؟!!! کسی نظری داره

(۱۳ دى ۱۳۹۰ ۰۸:۲۳ ب.ظ)rad.bahar نوشته شده توسط:  در کتاب نیپولیتان فصل ۷ تمرین ۱ صفحه ۳۳۶ سوالی مشابه داده شده با این مضمون
فرض کنید که s,t دو ارایه m,n عنصری باشند الگوریتمی بنویسید که تمامی عناصر مشترک را پیدا کند و انها را در ارایه u ذخیره کند نشان دهید که این کار می تواند در زمان (n+m)تتا انجام شود
اگر چنین است پس جواب سوال کنکور( n)تتا است؟!!! کسی نظری داره

در مورد راه حلش توضیحی نداده ؟؟؟

فکر کنم این طوری حل بشه
یک لیست رو به جدول hash وارد می کنیم. برای n عنصر در زمانn وارد hash می شوند و بعد عناصر لیست دوم را در hash جستجو می کنیم برای هر عنصر میشه مرتبه ۱ وبرای nعنصر از مرتبه n .
پس بهترین حالت از مرتبه n است.
منبع‌:

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

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

---

(۱۹ بهمن ۱۳۹۰ ۰۸:۰۸ ب.ظ)saeedeh123 نوشته شده توسط:  فکر کنم این طوری حل بشه
یک لیست رو به جدول hash وارد می کنیم. برای n عنصر در زمانn وارد hash می شوند و بعد عناصر لیست دوم را در hash جستجو می کنیم برای هر عنصر میشه مرتبه ۱ وبرای nعنصر از مرتبه n .
پس بهترین حالت از مرتبه n است.
منبع‌:

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

ازمون حالت میانگین و بدترین رو خواسته