جواب این سوال چی میشه ؟؟؟؟
فکر می کنم تو بدترین حالت بشه با مرتبه nlgn به جواب رسید.به این صورت که:یکی از دو تا لیست رو مرتب کنید(با مرتبه nlgn).حالا هرکدوم از عناصر اون یکی لیست که نامرتب هستش رو بردارید و با باینری سرچ تو لیست مرتب پیداش کنید.در کل مرتبه این روشی که گفتم میشه:[tex]\Theta (nlgn) \Theta (nlgn)=\Theta (nlgn)[/tex]
(09 دى 1390 11:25 ق.ظ)mfXpert نوشته شده توسط: [ -> ]فکر می کنم تو بدترین حالت بشه با مرتبه nlgn به جواب رسید.به این صورت که:یکی از دو تا لیست رو مرتب کنید(با مرتبه nlgn).حالا هرکدوم از عناصر اون یکی لیست که نامرتب هستش رو بردارید و با باینری سرچ تو لیست مرتب پیداش کنید.در کل مرتبه این روشی که گفتم میشه:[tex]\Theta (nlgn) \Theta (nlgn)=\Theta (nlgn)[/tex]
تو بدترین حالت خودم هم همین رو بدست آوردم اما مشکل من تو حالت میانگینه که نمیدونم میشه همون nlognیا n حالت میانگین رو چه جوری در نظر بگیریم؟؟؟؟
نمیشه بگیم که دو لیست رو ادغام کنیم (به صورت نامرتب:یعنی یکی رو در انتهای دیگری قرار بدیم) بعد شروع کنیم BST بسازیم با این لیست 2n عنصری (که در بدترین حالت میشه با ارتفاع n و در بهترین حالت میشه با ارتفاع nlgn) و در حین ساختن BST عناصر تکراری رو پیدا میکنیم....
جوابش کدوم گزینه هست هما جان؟سوال چه سالی هست؟
(09 دى 1390 01:11 ب.ظ)NoOne نوشته شده توسط: [ -> ]نمیشه بگیم که دو لیست رو ادغام کنیم (به صورت نامرتب:یعنی یکی رو در انتهای دیگری قرار بدیم) بعد شروع کنیم BST بسازیم با این لیست ۲n عنصری (که در بدترین حالت میشه با ارتفاع n و در بهترین حالت میشه با ارتفاع nlgn) و در حین ساختن BST عناصر تکراری رو پیدا میکنیم....
جوابش کدوم گزینه هست هما جان؟سوال چه سالی هست؟
تست اول ساختمان داده 90 بوده
اینی که شما میگید حداقل nlog n هست (البته جواب رو به ما میده )
فکر کنم 2 بشه . اونایی که کتاب سنجش رو دارن لطفا جواب کتاب رو بزارن تا بررسی کنیم.
سوال ساختمان داده کنکور ۹۰
من خودم جواب رو نمیدونم
ولی فکر میکنم همین ۲ بشه ولی اینکه چه جوری میانگینش میشه O(n نمی تونم ثابت کنم
آقای masoud شما میشه بگید چه جوری گزینه‌ی ۲ رو بدست آوردید
یکی از بچه‌ها تو این لینک:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
گفته که این سوال حذف شده
(09 دى 1390 01:28 ب.ظ)homa نوشته شده توسط: [ -> ]سوال ساختمان داده کنکور ۹۰
من خودم جواب رو نمیدونم
ولی فکر میکنم همین ۲ بشه ولی اینکه چه جوری میانگینش میشه O(n نمی تونم ثابت کنم
آقای masoud شما میشه بگید چه جوری گزینه‌ی ۲ رو بدست آوردید
یکی از بچه‌ها تو این لینک:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
گفته که این سوال حذف شده
منم نمی تونم اثبات کنم برای همین گفتم فکر کنم 2 بشه
خوب با استدلال من میشه گفت گزینه 4میشه.کسی نظری نداره؟
(09 دى 1390 06:42 ب.ظ)NoOne نوشته شده توسط: [ -> ]خوب با استدلال من میشه گفت گزینه ۴میشه.کسی نظری نداره؟
اگه 2 نباشه 3 هست . آخه هر چی باشه با AVL در بدترین حالت در زمان nlog قابل پیاده سازیه
گزینه صحیح سه هست .
محال است در این سئوال بتوان به مرتبه ایی بهتر از nlgn دست یافت چه میانگین و چه بدترین حالت .
اصلا به راحتی میتوان اثبات کرد که الگوریتمی که بر مبنای مقایسه پایه ریزی شده باشه نمیتواند در زمان کمتر از nlgn اشتراک این دولیست را به دست اورد .
شاید طراح محترم فراموش کار بودن و یا این نکته رو فراموش کردن و یا اینکه خواستن به دواطلبان کنکور 90 حال درست و حسابی بدن .
جای بسی تاسف هست شاهد چنین مواردی هستیم که در یک سال دو تا سئوال از پنج تا سئوال ساختمان حذف بشه . این هم به نحوی حق ناس هست که حق هزاران نفر رو پایمال میکنه .
در حالت خاص میتوان به مرتبه n دست یافت اما این فقط در حالت خاص امکان پذیر هست و با روشهایی شبیه الگوریتمهای مرتب سازی خطی و غیره (مثلا با باکت بندی مناسب یا حتی در هم سازی) اما مسئله اینه که این تنها در حالتهای خاص امکان پذیر هست و زمانی که هر دولیست ما از یکی الگو خاص پیروی کنن . که در اینجا هیچ اطلاعی از عناصر لیست نداریم و تنها راه همان مرتب سازی در زمان Nlgn ودر نهایت بقیه ماجرا
در کتاب نیپولیتان فصل 7 تمرین 1 صفحه 336 سوالی مشابه داده شده با این مضمون
فرض کنید که s,t دو ارایه m,n عنصری باشند الگوریتمی بنویسید که تمامی عناصر مشترک را پیدا کند و انها را در ارایه u ذخیره کند نشان دهید که این کار می تواند در زمان (n+m)تتا انجام شود
اگر چنین است پس جواب سوال کنکور( n)تتا است؟!!! کسی نظری داره
(13 دى 1390 08:23 ب.ظ)rad.bahar نوشته شده توسط: [ -> ]در کتاب نیپولیتان فصل ۷ تمرین ۱ صفحه ۳۳۶ سوالی مشابه داده شده با این مضمون
فرض کنید که s,t دو ارایه m,n عنصری باشند الگوریتمی بنویسید که تمامی عناصر مشترک را پیدا کند و انها را در ارایه u ذخیره کند نشان دهید که این کار می تواند در زمان (n+m)تتا انجام شود
اگر چنین است پس جواب سوال کنکور( n)تتا است؟!!! کسی نظری داره
در مورد راه حلش توضیحی نداده ؟؟؟
فکر کنم این طوری حل بشه
یک لیست رو به جدول hash وارد می کنیم. برای n عنصر در زمانn وارد hash می شوند و بعد عناصر لیست دوم را در hash جستجو می کنیم برای هر عنصر میشه مرتبه ۱ وبرای nعنصر از مرتبه n .
پس بهترین حالت از مرتبه n است.
منبع:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
خب شاید از مرتب سازی مبنایی استفاده کرده
اگه نه علتش رو بگید
(19 بهمن 1390 08:08 ب.ظ)saeedeh123 نوشته شده توسط: [ -> ]فکر کنم این طوری حل بشه
یک لیست رو به جدول hash وارد می کنیم. برای n عنصر در زمانn وارد hash می شوند و بعد عناصر لیست دوم را در hash جستجو می کنیم برای هر عنصر میشه مرتبه ۱ وبرای nعنصر از مرتبه n .
پس بهترین حالت از مرتبه n است.
منبع:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ازمون حالت میانگین و بدترین رو خواسته