زمان کنونی: ۲۷ مهر ۱۳۹۷, ۰۳:۵۷ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

اشتراک لیست

ارسال:
  

homa پرسیده:

اشتراک لیست

جواب این سوال چی میشه ؟؟؟؟


فایل‌(های) پیوست شده

۰
ارسال:
  

mfXpert پاسخ داده:

RE: اشتراک لیست

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

ارسال:
  

homa پاسخ داده:

RE: اشتراک لیست

(۰۹ دى ۱۳۹۰ ۱۱:۲۵ ق.ظ)mfXpert نوشته شده توسط:  فکر می کنم تو بدترین حالت بشه با مرتبه nlgn به جواب رسید.به این صورت که:یکی از دو تا لیست رو مرتب کنید(با مرتبه nlgn).حالا هرکدوم از عناصر اون یکی لیست که نامرتب هستش رو بردارید و با باینری سرچ تو لیست مرتب پیداش کنید.در کل مرتبه این روشی که گفتم میشه:[tex]\Theta (nlgn) \Theta (nlgn)=\Theta (nlgn)[/tex]
تو بدترین حالت خودم هم همین رو بدست آوردم اما مشکل من تو حالت میانگینه که نمیدونم میشه همون nlognیا n حالت میانگین رو چه جوری در نظر بگیریم؟؟؟؟
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

Msccom پاسخ داده:

اشتراک لیست

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

ارسال:
  

Masoud05 پاسخ داده:

RE: اشتراک لیست

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

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

۰
ارسال:
  

Msccom پاسخ داده:

اشتراک لیست

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

ارسال:
  

Masoud05 پاسخ داده:

RE: اشتراک لیست

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

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

۰
ارسال:
  

پشتکار پاسخ داده:

اشتراک لیست

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

۰
ارسال:
  

hadi_m پاسخ داده:

اشتراک لیست

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

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

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

۰
ارسال: #۱۰
  

rad.bahar پاسخ داده:

اشتراک لیست

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

ارسال: #۱۱
  

homa پاسخ داده:

RE: اشتراک لیست

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

در مورد راه حلش توضیحی نداده ؟؟؟
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۲
  

Aurora پاسخ داده:

RE: اشتراک لیست

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

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

۰
ارسال: #۱۳
  

پشتکار پاسخ داده:

اشتراک لیست

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

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  لیست مجاورتی homa ۱ ۱,۰۱۶ ۱۳ آذر ۱۳۹۰ ۰۹:۱۷ ب.ظ
آخرین ارسال: مازیار صفایی

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close