اشتراک لیست - نسخهی قابل چاپ صفحهها: ۱ ۲ |
اشتراک لیست - homa - 09 دى ۱۳۹۰ ۰۹:۱۷ ق.ظ
جواب این سوال چی میشه ؟؟؟؟ |
RE: اشتراک لیست - mfXpert - 09 دى ۱۳۹۰ ۱۱:۲۵ ق.ظ
فکر می کنم تو بدترین حالت بشه با مرتبه nlgn به جواب رسید.به این صورت که:یکی از دو تا لیست رو مرتب کنید(با مرتبه nlgn).حالا هرکدوم از عناصر اون یکی لیست که نامرتب هستش رو بردارید و با باینری سرچ تو لیست مرتب پیداش کنید.در کل مرتبه این روشی که گفتم میشه:[tex]\Theta (nlgn) \Theta (nlgn)=\Theta (nlgn)[/tex] |
RE: اشتراک لیست - homa - 09 دى ۱۳۹۰ ۱۱:۵۰ ق.ظ
(۰۹ دى ۱۳۹۰ ۱۱:۲۵ ق.ظ)mfXpert نوشته شده توسط: فکر می کنم تو بدترین حالت بشه با مرتبه nlgn به جواب رسید.به این صورت که:یکی از دو تا لیست رو مرتب کنید(با مرتبه nlgn).حالا هرکدوم از عناصر اون یکی لیست که نامرتب هستش رو بردارید و با باینری سرچ تو لیست مرتب پیداش کنید.در کل مرتبه این روشی که گفتم میشه:[tex]\Theta (nlgn) \Theta (nlgn)=\Theta (nlgn)[/tex]تو بدترین حالت خودم هم همین رو بدست آوردم اما مشکل من تو حالت میانگینه که نمیدونم میشه همون nlognیا n حالت میانگین رو چه جوری در نظر بگیریم؟؟؟؟ |
اشتراک لیست - Msccom - 09 دى ۱۳۹۰ ۰۱:۱۱ ب.ظ
نمیشه بگیم که دو لیست رو ادغام کنیم (به صورت نامرتب:یعنی یکی رو در انتهای دیگری قرار بدیم) بعد شروع کنیم BST بسازیم با این لیست ۲n عنصری (که در بدترین حالت میشه با ارتفاع n و در بهترین حالت میشه با ارتفاع nlgn) و در حین ساختن BST عناصر تکراری رو پیدا میکنیم.... جوابش کدوم گزینه هست هما جان؟سوال چه سالی هست؟ |
RE: اشتراک لیست - Masoud05 - 09 دى ۱۳۹۰ ۰۱:۲۰ ب.ظ
(۰۹ دى ۱۳۹۰ ۰۱:۱۱ ب.ظ)NoOne نوشته شده توسط: نمیشه بگیم که دو لیست رو ادغام کنیم (به صورت نامرتب:یعنی یکی رو در انتهای دیگری قرار بدیم) بعد شروع کنیم BST بسازیم با این لیست ۲n عنصری (که در بدترین حالت میشه با ارتفاع n و در بهترین حالت میشه با ارتفاع nlgn) و در حین ساختن BST عناصر تکراری رو پیدا میکنیم....تست اول ساختمان داده ۹۰ بوده اینی که شما میگید حداقل nlog n هست (البته جواب رو به ما میده ) فکر کنم ۲ بشه . اونایی که کتاب سنجش رو دارن لطفا جواب کتاب رو بزارن تا بررسی کنیم. |
RE: اشتراک لیست - homa - 09 دى ۱۳۹۰ ۰۱:۲۸ ب.ظ
سوال ساختمان داده کنکور ۹۰ من خودم جواب رو نمیدونم ولی فکر میکنم همین ۲ بشه ولی اینکه چه جوری میانگینش میشه O(n نمی تونم ثابت کنم آقای masoud شما میشه بگید چه جوری گزینهی ۲ رو بدست آوردید یکی از بچهها تو این لینک: مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید. گفته که این سوال حذف شده |
RE: اشتراک لیست - Masoud05 - 09 دى ۱۳۹۰ ۰۴:۰۲ ب.ظ
(۰۹ دى ۱۳۹۰ ۰۱:۲۸ ب.ظ)homa نوشته شده توسط: سوال ساختمان داده کنکور ۹۰ منم نمی تونم اثبات کنم برای همین گفتم فکر کنم ۲ بشه |
اشتراک لیست - Msccom - 09 دى ۱۳۹۰ ۰۶:۴۲ ب.ظ
خوب با استدلال من میشه گفت گزینه ۴میشه.کسی نظری نداره؟ |
RE: اشتراک لیست - Masoud05 - 09 دى ۱۳۹۰ ۰۶:۵۳ ب.ظ
(۰۹ دى ۱۳۹۰ ۰۶:۴۲ ب.ظ)NoOne نوشته شده توسط: خوب با استدلال من میشه گفت گزینه ۴میشه.کسی نظری نداره؟ اگه ۲ نباشه ۳ هست . آخه هر چی باشه با AVL در بدترین حالت در زمان nlog قابل پیاده سازیه |
اشتراک لیست - پشتکار - ۰۹ دى ۱۳۹۰ ۰۹:۳۸ ب.ظ
این سوال حذف شده |
اشتراک لیست - hadi_m - 10 دى ۱۳۹۰ ۰۴:۲۷ ب.ظ
گزینه صحیح سه هست . محال است در این سئوال بتوان به مرتبه ایی بهتر از nlgn دست یافت چه میانگین و چه بدترین حالت . اصلا به راحتی میتوان اثبات کرد که الگوریتمی که بر مبنای مقایسه پایه ریزی شده باشه نمیتواند در زمان کمتر از nlgn اشتراک این دولیست را به دست اورد . شاید طراح محترم فراموش کار بودن و یا این نکته رو فراموش کردن و یا اینکه خواستن به دواطلبان کنکور ۹۰ حال درست و حسابی بدن . جای بسی تاسف هست شاهد چنین مواردی هستیم که در یک سال دو تا سئوال از پنج تا سئوال ساختمان حذف بشه . این هم به نحوی حق ناس هست که حق هزاران نفر رو پایمال میکنه . در حالت خاص میتوان به مرتبه n دست یافت اما این فقط در حالت خاص امکان پذیر هست و با روشهایی شبیه الگوریتمهای مرتب سازی خطی و غیره (مثلا با باکت بندی مناسب یا حتی در هم سازی) اما مسئله اینه که این تنها در حالتهای خاص امکان پذیر هست و زمانی که هر دولیست ما از یکی الگو خاص پیروی کنن . که در اینجا هیچ اطلاعی از عناصر لیست نداریم و تنها راه همان مرتب سازی در زمان Nlgn ودر نهایت بقیه ماجرا |
اشتراک لیست - rad.bahar - 13 دى ۱۳۹۰ ۰۸:۲۳ ب.ظ
در کتاب نیپولیتان فصل ۷ تمرین ۱ صفحه ۳۳۶ سوالی مشابه داده شده با این مضمون فرض کنید که s,t دو ارایه m,n عنصری باشند الگوریتمی بنویسید که تمامی عناصر مشترک را پیدا کند و انها را در ارایه u ذخیره کند نشان دهید که این کار می تواند در زمان (n+m)تتا انجام شود اگر چنین است پس جواب سوال کنکور( n)تتا است؟!!! کسی نظری داره |
RE: اشتراک لیست - homa - 19 بهمن ۱۳۹۰ ۰۴:۵۸ ب.ظ
(۱۳ دى ۱۳۹۰ ۰۸:۲۳ ب.ظ)rad.bahar نوشته شده توسط: در کتاب نیپولیتان فصل ۷ تمرین ۱ صفحه ۳۳۶ سوالی مشابه داده شده با این مضمون در مورد راه حلش توضیحی نداده ؟؟؟ |
RE: اشتراک لیست - Aurora - 19 بهمن ۱۳۹۰ ۰۸:۰۸ ب.ظ
فکر کنم این طوری حل بشه یک لیست رو به جدول hash وارد می کنیم. برای n عنصر در زمانn وارد hash می شوند و بعد عناصر لیست دوم را در hash جستجو می کنیم برای هر عنصر میشه مرتبه ۱ وبرای nعنصر از مرتبه n . پس بهترین حالت از مرتبه n است. منبع: مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید. |
اشتراک لیست - پشتکار - ۱۹ بهمن ۱۳۹۰ ۰۸:۲۵ ب.ظ
خب شاید از مرتب سازی مبنایی استفاده کرده اگه نه علتش رو بگید (۱۹ بهمن ۱۳۹۰ ۰۸:۰۸ ب.ظ)saeedeh123 نوشته شده توسط: فکر کنم این طوری حل بشه ازمون حالت میانگین و بدترین رو خواسته |